Plenary:Pseudo-codewords and iterative decoding: A Guided tour.
by Pascal Vontobel.

Pascal gave a very nice tutorial presentation of the recent results on Linear programming decoding, its relations to iterative decoding through graph covers (the eagle vs the mountain lion) and the role of the vertices of the fundamental polytope called pseudo-codewords. I saw that the slides are available online on the pseudo-codewords homepage and contain many interesting figures like the decision regions and numerous graph cover examples.

On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks
by Salim Y. El Rouayheb, Mohammad Asad R. Chaudhry, and Alex Sprintson

This paper studies the ‘Single-hop’ wireless Network coding problem where a base station is trying to communicate a number of packets to a set of receivers. Each of the receivers has (say, from previous transmissions) a subset of the packets, and a list of desired packets it wants to receive. The question is finding the minimal number of transmissions for the base station (each transmission is overheard by all the receivers) so that all the clients can decode the packets they are interested in. For example, if receiver R1 has packets A and wants B while R2 has B and wants A, a single transmission of A+B will suffice. Salim showed that finding the minimal number of transmissions for a general set of receivers is NP-hard over GF(2). Further, the minimal number of transmissions is non-monotone in the field size and can depend on the characteristic of the field (which was quite surprising to me- I was guessing that there would exist a field size large enough above which there would be no difference). They also show how a special case of this problem (assuming no memory at the decoders) boils down to clique partition and propose a simple algorithm that works well for random instances.

Fault Tolerant Memories Based on Expander Graphs
by Shashi Kiran Chilappagari and Bane Vasic

This paper looked at the problem of maintaining an erasure encoded representation when both the memory elements and the logical gates can be faulty. As far as I understood, there is a correcting circuit that periodically checks for faults in the memory and repairs them using the bit-flipping algorithm of Sipser and Spielman. The problem is that this circuit is made of unreliable logic gates and hence the repairs are not always correct. If the Tanner graph of the code used has sufficient expansion, then the correcting circuit manages (despite its own errors) to keep the fraction of errors below a threshold.
This threshold is low enough for a powerful decoder (that makes no errors) to be able to recover all the bits at any given time- whereas a memory with no correction circuit would always fail after a constant amount of time.

Reducing the Error Floor
Michael Chertkov

Misha presented improved decoding algorithms (based on LP decoding) to reduce the probability of error at high SNR (error floor). The talk focused on the famous [155,64,20] Tanner code where the authors have developed an algorithm to find the most dangerous (low pseudo-weight) pseudo-codewords. The proposed Loop Guided Guessing (LGG) is an informed facet guessing algorithm that selects which bits to guess by finding critical loops on the graph. It was great to learn that the investigated algorithms managed to correct all 200 low weight pseudo-codewords-essentially achieving ML performance for high SNR.

On Optimizing XOR-Based Codes for Fault-Tolerant Storage Applications
Cheng Huang, Jin Li, and Minghua Chen

This paper shows a novel technique to improve the performance of encoding and decoding for linear codes that have been reduced to binary representations. The encoding and decoding of linear block codes is represented in matrix form, where the matrices are fixed while the vectors are data dependent. The idea is finding patterns in the matrices that can be reused, essentially optimizing the number of XOR operations required to multiply any vector with a given matrix. For example is the parities P1= x1+x3+x5, P2=x1+x3+x5+x6, P6=x2+x3+x4+x5 are computed naively, this requires 8 XOR operations. If one pre-computes x3+x5, only 6 XOR operations suffice. The authors call this common operations first (COF) principle and propose an optimization problem to minimize the number of XORs required to multiply a given matrix with any vector. They propose two greedy algorithms that work well in practice and show that generic Reed-Solomon codes that have been optimized with this scheme can be equally or more efficient than codes specifically designed to minimize the number of XOR operations.

Approximate message-passing inference algorithm
Kyomin Jung and Devavrat Shah

Devavrat presented a general message passing framework for computing maximum a-posteriori assignments (MAP) for binary markov random fields. Building on the recent result by Dror Weitz on the equivalence of message passing on a graph and a self-avoiding walk tree of G for marginalization, the equivalence still holds for MAP assignments. For graphs that admit some kind of good partitioning, Devavrat presented message passing algorithms that can approximate the MAP assignment within epsilon factor in polynomial time for any fixed epsilon. The intuition is that the graph can be separated in small components, compute estimates locally and then combine them to obtain a good global estimate. The algorithm can be applied to a wide family of graphs that can be easily separated (examples included planar graphs and graphs that have some types of geometry).

Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs, Sujay Sanghavi

Sujay showed that the max-product algorithm for finding weighted matchings in general graphs converges to the right answer if and only if the LP relaxation of the problem is tight. The proof relies on the fact that max-product is solving the problem on a computation tree that can sometimes contain extra matchings (pseudo-matchings!) of larger weight, that do not exist on the real graph. Using LP duality, Sujay showed that if the LP relaxation is tight, there are no such evil matchings on the computation tree. The converse (as far as i understood) is using a combinatorial characterization of when the LP relaxation fails- the existence of evil structures in the graph (‘Bad stemmed blossom’ and ‘bad blossom pair’) that also make max-product fail.

On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
Andrew McGregor and Olgica Milenkovic

Olgica presented hardness results for minimum distance, minimum stopping and trapping sets for general linear codes and even LDPC codes. In particular she showed that minimum stopping and trapping sets are hard to approximate within an arbitrary constant factor (in other words, there exists a factor c below which c-factor approximations become NP-hard). The reductions carry through even if the codes have constant degrees (LDPC) with minimum degree 3. An interesting related open problem I was thinking about after this talk is hardness results on finding and approximating minimum (BSC) pseudo-weight. Any ideas on this?

• Plenary Talk: Source and Channel Coding: Theory, Practice and System Aspects (Giuseppe Caire)

  This focus of this talk was on the benefits of using joint source channel coding for more “practical” systems. The main motivation was the catastrophic behavior of excess channel errors on source reconstruction. If you optimally compress an image and send it over a noisy channel, the reconstruction becomes terrible if the channel is a bit noisier than you expected. Since wireless channel variations are a real problem, this can have a real impact. Can we have a graceful degradation in the reconstruction quality via JSSC? He also gave two more examples, one from beamforming on the MIMO broadcast channel, and one about multicasting a Gaussian source over a Gaussian MAC using a Costa-like layering construction.

• The Case for Structured Random Codes in Network Communication Theorems (Bobak Nazer and Michael Gastpar)

  This paper focused on giving some motivations for exploiting a structured approach to random codes, rather than the standard information theoretic constructions we all know and love. For problems such as computing over a multiple-access channel, linear network coding, or interference networks, separating source and channel coding can result in performance losses. A simple scheme based on lattices can get better performance in these cases.

• On Separation in the Presence of Feedback (Haim Permuter and Tsachy Weissman)

  It is well-known that separation is optimal for point-to-point channels and that the directed mutual information gives the capacity of channels with feedback. For ergodic channels, they show that for construction with distortion D the condition C_FB > R(D) is necessary and sufficient, which shows that separation is optimal in this setting as well. For certain MACs which can be decomposed into a “multiplexer plus point-to-point” channel, they can show a similar result. In the talk they also looked at a binary MAC with stationary ergodic noise and feedback, and showed that separation is optimal there. Their results extend to mod-additive MACs.

• Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs (Sujay Sanghavi)

  The problem of maximum weight matching in a graph with edge weights is to find the largest weight set of disjoint edges. One algorithm for doing this is max-product, which is an iterative message passing algorithm. The matching problem can also be posed as an integer program, which has a linear programming relaxation. Sujay shows that the performance of max-product is tied to the tightness of the LP — if the LP is tight then MP converges to the correct answer, and if the LP is loose then MP will not converge. This provides a nice guarantee of when MP will converge that ties together the iterative and linear-programming approaches to optimization on graphs. Clearly this has relations to decoding, but I’ll let Alex comment on those.

• On the Duality and Difference Between Slepian-Wolf Coding and Channel Coding (Jun Chen, Da-ke He, Ashish Jagmohan, and Luis A. Lastras-Montano)

  This paper explored the similarities between channel coding and Slepian-Wolf coding. The comment made by Jun Chen at the talk was that the “difference” mentioned in the title is actually another kind of duality. By duality, they are referring to a kind of mirror pairing of the error exponents for source and channel coding. Using relations between linear coding strategies shows that nonlinear Slepian Wolf codes can strictly outperform linear codes.

• On Network Interference Management (Aleksandar Jovicic, Hua Wang, and Pramod Viswanath)

  This paper looked at two basic interference patterns — one long range link causing problems for many short range links, and one long range link experiencing interference from many short links. The question is this — is orthogonalization/degree-of-freedom sharing/reuse optimal? They characterize the high SNR degree-of-freedom range for both scenarios using a multi-layer superposition coding scheme and use genie-aided converse arguments to get a “within one bit” characterization in the spirit of the Etkin/Tse/Wang approach to interference channels. In the latter interference model they also show that power control can get similar performance.

• Capacity for Classes of Broadcast Channels with Receiver Side Information (Gerhard Kramer and Shlomo Shamai (Shitz))

  The channel model here is a broadcast channel where each user has as side information the other user’s message. The coding schemes used are nested lattice codes, and they show that they can get all capacity points — furthermore they can generalize their scheme to cost-constrained channels and coding for degraded message sets. At the end of the talk there was some very recent work by a student working with Gerhard (Wei Kang, I believe?) who showed a similar result for the case of general correlated sources with a certain kind of degraded side information at one receiver.

• Successive Refinement of Vector Sources under Individual Distortion Criteria (Jayanth Nayak, Ertem Tuncel, Deniz Gunduz, and Elza Erkip)

  The problem here is to make a successive refinement code (if you get more of the codeword you can decode to lower distortion) for vector sources where we have a distortion constraint on each of the components of the code. If we look at a two sources (vectors of length 2) we can mark achievable distortion pairs (D₁, D₂) on the plane and ask “what kind of trajectory can we make with successive refinement codes? It turns out the answer is rather complicated — for Gaussian sources we get three regions and there are rules about what paths we can take.

• On Cognitive Interference Networks (Amos Lapidoth, Shlomo Shamai (Shitz), and Michele A. Wigger)

  This is a follow-up to the ISIT paper, which focused on characterizing the pre-log of the sum-capacity of a certain interference network that looked like a chain. The “cognitive” aspect of the problem is that the transmitters know the message of their interfering neighbors. They can use some linear encoding to zero-force their own interference and then a number of results pop out — conditions on when the pre-log for K users can be K or K-1, necessary and sufficient conditions on the network for achieving K, and the fact that pre-log can be noninteger, unlike the case where no side information is available.

• Reliable Communication in Networks with Multi-access Interference (Danail Traskov and Gerhard Kramer)

  Danail presented an interesting scheme for generating correlated messages in networks (with an eye to network coding, it seemed). As a simple example, a source transmitter sends rate-constrained messages to two relays who then communicate to the destination. This is similar to the Schein-Gallager network but without the broadcast component at the beginning. The source can correlate the messages at the relays, and in some cases they can get a capacity result. More importantly, the scheme scales to more general networks of MACs and has a nice “flow” interpretation.

A lot of my comments will be short since in retrospect my notes were quite poor for most of the talks I attended. I attribute it to fatigue… I also skipped out on a number of talks to think over some new problems that had come to mind. I’m going to let Alex blog about some of the coding talks.

• Plenary Talk: On Modeling Distributions over Large Alphabets (Alon Orlitsky)

  Orlitsky started with the non-paradoxical nature of the “birthday paradox.” After querying people in the audience one by one, he finally ended with two people who had the same birthday (9/3), namely Shlomo Shamai and Rüdiger Urbanke. This was all a set-up of course, but I honestly thought Urbanke was just sick of the process and tried to end it. One way of turning the birthday paradox on its head is to ask “if we saw that it took K queries to find two people with the same birthday, how should we estimate the length of the year?” This is precisely the problem of large alphabet size estimation with small sample size. He then went on to tour the techniques of patterns, profiles, and the relation to capture-recapture statistics. I had seen a lot of this work before, but it was nice to see it again and a bit more slowly.

• Power Allocation for Discrete-Input Non-Ergodic Block-Fading Channels (Khoa D. Nguyen, Albert Guillén i Fàbregas, and Lars K. Rasmussen)

  This work was about finding the SNR exponent of the outage probability for power allocation strategies over a particular class of fading channels (Nakagami). They differentiated between long-term and short-term power allocation and found a relationship between the short-term optimal scheme and a Singleton bound. The more interesting part is that suboptimal, lower complexity schemes are nearly optimal in this outage-exponent sense.

• Probabilistic Capacity and Optimal Coding for Asynchronous Channel (Ning Cai, Siu-Wai Ho, and Raymond W. Yeung)

  This paper looked at time jitter in a continuous time model, and showed that run-length limited (RLL) codes are suboptimal for this kind of asynchrony. When the jitter is bounded in some sense they found 0-error codes, and showed that “interval codes” are better than RLL codes. They used an approximation for the rate loss involving characteristic functions in the case where we demand a bound on the time that the encoder and decoder can be out of synch. They come up with a channel model and capacity formulation and design new capacity achieving codes.

• The Effect of Finite Memory on Throughput of Wireline Packet Networks (Badri N. Vellambi, Nazanin Rahnavard, and Faramarz Fekri)

  In a packet erasure network on a line, with finite buffer sizes at the nodes, what are the benefits of network coding? The authors came up with a large Markov chain model and have to find the steady state distribution to get the capacity of the network. Unfortunately, the chain is a bit unwieldy so they come up with approximations for the distribution. Some simulations are also provided.

I went to all the plenaries this year except Vince Poor’s (because I was still sick and trying to get over it). I was a bit surprised this year that the first three speakers were all from within the IT community — I had been used to the plenaries giving an outsider’s perspective on problems related to information theory. The one speaker from outside, Emery Brown, was asked by Andrea Goldsmith “what can information theorists do to help your field?” I learned a lot from the talks this year though, and the familiarity of the material made it a more gentle introduction to the day for my sleepy brain.

Michelle Effros talked about Network Source Coding, asking three questions : what is a network source code, why does the network matter, and what if separation fails? She emphasized that in the latter case, bits and data rate are still useful abstractions for doing negotiations with higher layers of the network stack. For me, this brought up an interesting question — are there other currencies that may also make sense for wireless applications, for example? Her major proposal for moving forward was to “question the questions.” Instead of asking “what is the capacity region” we can ask “is the given rate tuple supportable?” She also emphasized the importance of creating a hierarchy of problem reductions (as in complexity theory). To me, that is already happening, so it didn’t seem like news, but maybe the idea was to formalize it a bit more (c.f. The Complexity Zoo). The other proposal, also related to CS theory, was to come up with epsilon-approximation arguments. The reason this might be useful is that it is hard in general to implement “optimal” code constructions, and she gave an example from her own work of finding a (1 + epsilon)-approximation for vector quantization.

Shlomo Shamai talked about the Gaussian broadcast channel, discussing first the basics, degradation, and superposition, and then how fading makes the whole problem much more difficult. He apologized in advance for supposedly providing an idiosyncratic look at the problem, but I thought it was an excellent survey. Although he pointed out a number of important open problems in broadcasting (how can we show Gaussian inputs are optimal?), I was hoping he would make more of a call to arms or something. Of course, on Tuesday I was heavily feverish and miserable, so I most likely missed a major point in his talk.

As I said, I missed Vince Poor’s talk, but I think I saw a version of the same material at the Başarfest, and it used game theory methods to study resource allocation for networks (like power allocation). I needed the extra rest to get healthy, though.

Sergio Verdú gave the Shannon Lecture, and titled his talk “teaching it.” He made a few new proposals for how information theory should be taught and presented. One of the strengths he identified was the number of good textbooks which have come out about Information Theory, many of which were written by previous Shannon lecturers. If I had to sum up the main changes he proposed, it was to de-emphasize the asymptotic equipartition property (AEP), separate fixed-blocklength analysis from asymptotics, don’t present only memoryless sources and channels, and provide more operational characterizations of information quantities. He drew on a number of examples of simplified proofs, ways of getting bit-error converses without Fano’s Inequality, the importance of the KL-divergence, the theory of output statistics, and the usefulness of the normal approximation in information theory. I agreed with a lot of his statements from a “beauty of the subject” point of view, but I don’t know that it would make information theory more accessible to others, necessarily.

Emery Brown gave the only non-information theory talk: he addressed how to design signal processing algorithms to decipher brain function. Starting from point processes and their discretization to get spike functions and rate functions, he gave specific examples of trying to figure out how to track “place memory” neurons in the rat hippocampus. The hippocampus contains neurons that remember places (and also orientation) — after walking through some example of mazes in which a neuron would fire only going one direction down a particular segment of the maze, he showed an experiment of a rat running around a circular area and tried to use the measurements on a set of neurons to infer the position of the mouse. Standard “revcor” analysis just does a least squares regression of spikes onto position to get a model, but he used a state-space model to address the dynamics and some Bayesian inference methods to get significantly better performance. He then turned to how we should model the receptive field of a neuron evoloving over time as a rat learns a task. When asked about what information theorists can bring to the table, he said that getting into a wet lab and working directly with experimentalists and bringing a more principled use of information measures in neuroscience data analysis would be great contributions. It was a really interesting talk, and I wish the crowd had been larger for it.

A Linear Interference Network with Local Side-Information (M. Wigger, S. Shamai (Shitz), and A. Lapidoth) : This model was a chain ofinterference channels with K total transmit-receive pairs in a kind of ladder, and looked at behavior of the prelog in the sum-capacity expression when each transmitter knows the J earlier messages in the ladder. For the achievable scheme, they silence some of the sensors and use dirty paper coding, and for the converse they use some interference-cancellation arguments. The bounds match and they get floor(K/(J+2)) for the prelog.

A Broadcast Approach to Multiple Access with Random States (P. Minero and D. Tse) : This paper looks at a kind of “compound MAC” problem, when the receiver has channel information (about the fading state for example). If the encoded information is “layered” via superposition coding, the decoder can opportunistically extract the data at a rate that the channel can support. By making each setting of the states into one virtual receiver, we get a broadcast version of the MAC. They look at two problems — the slow fading compound channel problem, and the “random access” model, where the number of users is variable. For the fading system, superposition is optimal for the sum rate, but for random access it is not.

On InterFerence Channel with Generalized Feedback (IFC-GF) (D. Tuninetti) : This looks at an interference channel with two additional outputs that are fed back to the transmitters. These outputs could be some internal part of the channel, or could be a noisy version of the channel outputs. For a Gaussian setting with the feedback being independently faded and noisy copies of the other transmitter’s signal, she exhibited a block Markov encoding scheme using backward decoding and showed that if there a common message can get a power boost.

Bounds on the capacity region of a class of interference channels (I. Telatar and D. Tse) : Although this talk was the last talk of the conference and I was pretty exhausted, it was one of my favorites. The class of channels being references are those in which the interference for user 1 is user 2’s signal passed through a channel and then a deterministic function. For example the channel could be “fade and add noise.” They derive outer bounds that are quite similar in form to the inner bound due to Chong-Motani-Garg, and can give some bounds on the tightness of that achievable region in the flavor of the “within 1-bit” result of Etkin-Tse-Wang.

Fingerprinting Capacity Under the Marking Assumption (N. Prasanth Anthapadmanabhan, Alexander Barg, and Ilya Dumer) : This is a cool problem that was new to me and uses some AVC-like techniques so I was quite excited about it. Suppose we have an original version of some data. We would like to make many copies with fingerprints and distribute them such that if any t recipients collude (the “pirates”), they cannot make a fake new copy that will fool a validating agent. The marking assumption is that the pirates cannot change the fingerprint except in places where their copies differ. This is a tough combinatorial problem but is amenable to some random coding arguments. In particular, they get upper and lower bounds on the case of 2 or 3 pirates for binary alphabets.

On Multiterminal Secrecy Capacities (Imre Csiszár and Prakash Narayan) : I talked about some of this work from ITA — this was quite similar, but since it was my second time seeing some of the material, I got a bit more out of it. One basic problem from this paper is this : a public “server” terminal broadcasts a message to a bunch of receivers, who then engage in public discussion. How large a key can they generate, given that the public communication is subject to eavesdropping? The most interesting technical detail for me was the use of Markov trees for the case where some of the receivers are also wiretapped.

On Oblivious Transfer Capacity (Imre Csiszár and Rudolf Ahlswede) : This talk was the only one I saw given on transparencies — Csiszár apologized for giving a talk on “old technology” but noted that the “topic is quite new.” The Oblivious Transfer problem is this : Alice has two strings, X and Y, each of which is k bits long. Bob has a binary variable Z which tells him in which string he is interested (0 for X and 1 for Y). Bob wants to get his string, but doesn’t want to let Alice know which one he wanted, and Alice wants to tell him the correct string without revealing anything about the one he didn’t want. Alice can communicate over a DMC and there is also noiseless two-way communication. The capacity is defined as the limit of k/n, where k is the maximum achievable k. They get bounds on the OT capacity, which in some cases are tight, but under the assumption that Alice and Bob do not try to “cheat.”

An Achievable Region of Gaussian Wiretap Channel with Side Information (Yanling Chen and A.J. Han Vinck) : This paper looks at the wiretapping problem where an additive channel interference term is known at the encoder. In this setting, a generalized Costa “dirty paper” coding scheme can be shown to mask the source signal from a wiretapper (giving high equivocation) while communicating over the channel as if the interference were not present. They conjecture that this scheme is optimal, but as usual in more complicated coding scenarios, the converses are a little harder to come by.

Shannon’s Secrecy System With Informed Receivers and its Application to Systematic Coding for Wiretapped Channels (Neri Merhav) : This studies the case where an iid source vector to be encoded at the transmitter is observed in two ways by the decoder — firstly via an iid correlated sequence of variables, and secondly via an encoded message sent via the encoder over a DMC. The wiretapper gets a degraded version of both of these variables. One key message from the talk was that systematic coding is sometimes as good as the “optimal” scheme in an equivocation sense.

Scaling Bounds for Function Computation over Large Networks (Sundar Subramanian, Piyush Gupta, and Sanjay Shakkottai) : This paper essentially looked at the scaling laws for the “refresh rate” of networks in which a collector node wants to compute a function f(x₁, x₁, …, x_n) of measurements at the nodes of a network. The network has bounded degree and there is a difference in scaling between type-sensitive (mean, mode) and type-threshold (max, min) functions. They show that deterministic bounds on type-sensitive functions are not possible in general, but probabilistic bounds are possible. By using a joint source-channel coding strategy, for AWGN networks they obtain constant refresh rates for small path-loss exponents.

Characterization of the Critical Density for Percolation in Random Geometric Graphs (Zhenning Kong and Edmund M. Yeh) : Since we had a reading group on percolation theory this semester, this talk felt right up my alley. Although using Monte Carlo techniques we know the critical threshold (density) for percolation (formation of a giant connected component) to happen in random geometric graphs, the analytical bounds are quite loose. This paper gets tighter analytical bounds by doing some smarter bounding of the “cluster coefficients,” which come from looking at the geometry of the percolation model.

Communication with Feedback via Posterior Matching (Ofer Shayevitz and Meir Feder) : This work was an attempt to come up with a common framework and generalization of the Horstein and Schalkwijk-Kailath feedback coding schemes, in which the encoder uses the feedback to track the decoder and “steer” it to the correct message. They come up with an idea, called “posterior matching” and apply it to DMCs to show that a simple “steering” encoder can also achieve the empirical mutual information of the channel I(Q,W) using the posterior CDF at the decoder. It’s a pretty cool result, in the line of “A is like B in this way,”

Broadcasting with Feedback (Sibi Raj Bhaskaran) : This addresses the question of broadcasting when feedback is only available to one user. In a degraded Gaussian broadcast setting, if the feedback is from the strong user, you can use a Gaussian codebook for the weak user with a Schalkwijk-Kailath scheme for the strong user to get an increased capacity region. This is one of those papers that I’ll have to read a bit more carefully…

The Gaussian Channel with Noisy Feedback (Young-Han Kim, Amos Lapidoth, and Tsachy Weissman) : This talk was about error exponents for the AWGN channel with noisy feedback. By using some change-of-measure and genie arguments, they show a non-trivial upper bound, and a three-phase coding scheme can give a lower bound which scales like (feedback noise variance)^-1. Unlike the perfect feedback case, where the exponent is infinite, both bound are finite. Furthermore, they show that linear coding for noisy feedback will not get any rate.

Error Exponent for Gaussian Channels with Partial Sequential Feedback (Manish Agarwal, Dongning Guo, and Michael L. Honig) : In this talk, they take an AWGN channel in which only a fraction of the received symbols are fed back and ask for the error exponent. They propose an achievable scheme that uses the slots with feedback separately from the slots without. With feedback, they try to steer the decoder into a favorable position. and then use a forward error-correcting code to get the rest of the rate.

A Coding Theorem for a Class of Stationary Channels with Feedback (Young-Han Kim) : The class of channels under consideration are those in which there is order m memory, and in this case the capacity is given by a normalized directed mutual information. The main interest for me was in the proof strategy, which used Shannon strategies and something called the “Nedoma decomposition,” which I have to read about a bit more… except that it’s in German, so I have to brush up my German first.

Capacity of Markov Channels with Partial State Feedback (Serdar Yüksel and Sekhar Tatikonda) : This was about partial feedback in that the state is quantized and sent back to the encoder. For a Markov state transition with some technical mixing conditions, they find a single-letter expression for the capacity with feedback, and that a sliding-window encoder is “almost good enough,” which is good news for practical coding schemes. They also use some nice dynamic programming with the directed mutual information as the running costs, which merits some closer inspection, I think.

Source Coding with Distortion through Graph Coloring (Vishal Doshi, Devavrat Shah, and Muriel Médard) : This paper looked at the rate-distortion function for reconstructing a function f(X,Y) with X at the encoder and Y as side information at the decoder. One can think of this as a “functional” Wyner-Ziv, or in some cases as a noisy Wyner-Ziv. In the lossless setting, the reconstruction function can be found using graph entropy, and minimum-entropy graph coloring turns out to be a way of obtaining a solution. For the lossy problem, they find a similar graph coloring scheme but can’t get a single-letter expression in all cases. What is interesting to me is the optimality of “preprocess + Slepian-Wolf,” which is similar in spirit to the work done by Wang, Wagner, Viswanath and others for Gaussian multiterminal source coding problems.

Compound conditional source coding, Slepian-Wolf list decoding, and applications to media coding (Stark C. Draper and Emin Martinian) : The main motivation here was that many multimedia applications (such as video coding) may more fruitfully be thought of as compound source coding problems with an unknown side information at the decoder. In this setting, we can imagine the side information as one of P different predictors of the source X available at the encoder. The encoder can use the different predictors to list decode the source message and send conditional list-disambiguation information in addition to the source encoding. It’s a neat scheme that seems quite related to some of my thesis work on list decoding for AVCs.

Correlated Sources over a Noisy Channel: Cooperation in the Wideband Limit (Chulhan Lee and Sriram Vishwanath) : I have to admit I didn’t fully get this talk, but it looked at wideband distributed source coding using “highly correlated sources.” They propose a modified PPM scheme which can exploit the correlation as if the encoding is joint with small bit error rate (but possibly larger block-error rate). What was unclear to me was why the modified error criterion was necessary, but it seems to be an artifact of the proposed scheme. The algorithm requires a sliding window decoder whose analysis seems a bit tricky.

Joint Universal Lossy Coding and Identification of Stationary Mixing Sources (Maxim Raginsky) : What is the loss in estimating the parameter of a source and doing universal lossy source coding? By using a competitive optimality framework and a Lagrangian formulation to trade off the parameter error and source distortion, Raginsky can bound the loss in performance. This falls into the category of the O(log n/sqrt(n)) results that I don’t know much about, but I will probably take a look at the full paper to get a better idea of how the codes work. He uses some ideas of VC dimension from learning theory, which I know a little about, so hopefully it will not be too hard going…

The source coding game with a cheating switcher (Hari Palaiyanur, Cheng Chang, Anant Sahai) : This is an extension of Berger’s source coding game, in which a switcher switches between k memoryless sources and you have to make a rate distortion code that can handle the worst case behavior of the switcher. Before, the switcher could not see the source outputs first. Here, he can (hence “cheating”). The main point is to figure out which iid distributions the switcher can emulate, and the worst one in that set gives the bound. The rest is a union bound over types and doesn’t affect the rate.