Allerton 2007 : Information Theory

Because Allerton proceedings don’t get handed out at the conference, my understanding of what I saw is upper bounded by the quality of my notes. If anyone has any clarifications or corrections, please let me know!

A Rate-Distortion Approach to Anonymous Networking
(Parvathinathan Venkitasubramaniam and Lang Tong)
This problem was looking at networks in which we want to keep eavesdropping nodes from doing traffic analysis. There is a technique called Chaum mixing that can be used by trusted routers to scramble traffic and increase anonymity. The measure of anonymity they use is an equivocation at the eavesdropper normalized by the entropy of the sessions. The problem then becomes a rate-distortion problem for scheduling sessions in the network. They use two classes of nodes, covert relays and normal relays, and try to find tradeoffs between the density of covert relays and the anonymity.

Wireless Network Information Flow
(Salman Avestimehr, Suhas Diggavi, and David Tse)
Suhas presented this paper, which was on the deterministic model that David presented at ITW. Since we have broadcast and multiple access in wireless networks, the signal interactions become quite complex. The deterministic model reduces these networks to deterministic finite-field networks, which have a simple cut-set upper bound in terms of the rank of associated matrices. This outer bound is achievable as well, so the capacity of this simplified model can be calculated and looks a bit like the Ford-Fulkerson theorem in a more general sense.

Source Coding with Mismatched Distortion Measures
(Urs Niesen, Devavrat Shah, and Gregory Wornell)
If the distortion measure that we are to use is not known at the time of encoding, what should we do? To be more concrete, suppose we have f and g as distortion measures. Given a rate R and distortion D for the source under distortion f, what is the smallest distortion Ewe can achieve under the same code with measure g? It can be arbitrarily bad! But we can also write the performance using a single-letter characterization. There was a second problem Urs discussed, bitu I didn’t quite catch it — I think it was fixing D under f and asking what E we can get under g, regardless of the rate.

A Deterministic Approach to Wireless Relay Networks
(Salman Avestimehr, Suhas Diggavi, and David Tse)
This was a continuation of the work in the earlier talk, providing the details of the proof. The first part shows that if all paths from source to sink in the network are of equal length, then the capacity is the cut-set bound. In order to deal with unequal length paths, they use a time expansion argument (which looked a bit like a trellis, actually) with scheduling to avoid different flows mixing. It’s a bit tricky to show that you get back to the cut set bound with this, but I assume the details are in the paper. The other part was to show that this model can be used to construct a scheme for the original Gaussian channel that is “close” to optimal, and that the maximum gap (one bit in many cases) occurs in a very small regime of parameters.

The Approximate Capacity of an One-Sided Gaussian Interference Channel
(Guy Bresler, Abhay Parekh, and David Tse)
This was yet another paper using the deterministic model, this time for the many-to-one (and by a clever duality argument on the interference pattern, the one-to-many) interference channel, in which one transmit-receive pair experiences (inflicts) interference from (on) everyone else. The central idea here is interference alignment — if one signal level experiences interference from a transmitter, it can experience interference from other transmitters with no problem (or so I understood it). Guy showed that the Han-Kobayashi scheme is not optimal because the interference pattern is “too crowded,” and gave a lattice-based scheme that emulates the deterministic model.