There were some talks on dynamic spectrum access as well as waterfilling and other resource allocation problems.

• Resource consumption in dynamic spectrum access networks: Applications and Shannon limits (Michael B. Pursley and Thomas C. Royster IV, Clemson University)

  This talk tried to address how to choose a modulation scheme to maximize throughput in dynamic spectrum access networks. The scheme could be power or bandwidth efficient, and trading off these efficiencies is important. One way of capturing the impact is to look at how the transmission of one radio affects other radios across bandwidth and time. So a radio preventing 3 radios talking over a 2 Hz for 1 second is using 6 units of “resource.” The limits on communication can be rephrased in terms of the familiar E_b/N₀.

• Spectrum sharing on a wideband fading channel with limited feedback (Manish Agarwal and Michael Honig, Northwestern University)

  Suppose that K users over N channels wish to share the spectrum effectively in a multiple-access setting. They can probe the channels to see which ones are available — if more than K’ probe a given channel, the destination can assign it for transmission. The goal is to choose a the number of channels to probe so that there is little overhead but users still get a fair allocation. At least that’s how I understood the problem. They show a scheme that probes N/(log N)^2 but the rate for each user grows like log(log N).

• Asynchronous iterative water-filling for Gaussian frequency-selective interference channels: A unified framework (Gesualdo Scutari, Univ. of Rome “La Sapienza”, Daniel P. Palomar, Hong Kong Univ. of Science and Technology, and Sergio Barbarossa, Univ. of Rome “La Sapienza”)

  This work looked at a new geometric intuition for the waterfilling algorithm for Gaussian channels, where the waterfilling allocation is a kind of projection onto a simplex. This projection view allows them to get convergence results for asynchronous waterfilling algorithms for the interference channels. The conditions for convergence match those for the multiple-access and broadcast channels.

• Spectrum sharing: fundamental limits and self-enforcing protocols. (Raul Etkin, U.C. Berkeley and HP-Labs)

  This talk focused on how to do interference management and generate self-enforcing protocols for spectrum-sharing systems. In the first part, he showed that a kind of Han-Kobayashi scheme gets to within 1 bit of the capacity region for the interference channel. The key is to show a tighter converse and comes from looking at certain genie-aided channels that are not too loose. The second part of the talk was a game-theoretic approach to guaranteeing good behavior in a spectrum-sharing system. The approach is to use punishments — if any user deviates from the protocol then the other users spread their power, punishing him. This game has an equilibrium and greatly improves on the static game, which has an unbounded price of anarchy. I just like writing that — “price of anarchy.”

I’m by no means an expert on coding theory, but I went to a few talks on coding that were interesting. Some were definitely geared for the specialist.

• Decoding LDPC codes through tree pruning (Yi Lu and Andrea Montanari, Stanford)

  This was one of those talks where I got the big picture and then lost the details, since I haven’t really studied LDPC decoding algorithms in sufficient detail. Their idea is to use a new construction/technique by Dror Weitz to compute the marginals in the graph of an LDPC code. The idea is to create a tree rooted at x_i whose marginal at the root is the same as the marginal at x_i in the original graph. This tree is constructed by taking self-avoiding random walks through the graph and putting a leaf when the walk crosses itself. But such a tree is too big — truncating at a fixed level gives an approximate algorithm for decoding.

• Communication over channels with varying sampling rate (Lara Dolecek, UC Berkeley)

  This paper looked at what happens when there is a sampling error in the received signal before the decoding block. Some symbol may be sampled twice or some symbol may be missed entirely and deleted. One way around this is to build better timing recovery blocks, and the other is to build better codes (which she does) that are resistent to these kind of repetition and deletion errors. This work comes up with number-theoretic formulation of the code design constraints, shows that existing codes can be modified to take into account these types of errors, as well as a modified belief-propagation decoding algorithm.

ITA coincided with NetCod07, which was a small miniworkshop (single-day, single-track) on network coding. I went to a few talks there, but unfortunately missed the one I most wanted to see, “Resilient network coding in the presence of Byzantine adversaries.” Oh well, at least there’s a paper for me to read.

• The benefits of network coding for peer-to-peer storage systems (Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright, Kannan Ramchandran, UC Berkeley)

  This talk was on designing a decentralized storage system in which individual nodes (peers) hold coded chunks of the total file. To be concrete, say we have a 8 MB file. Someone wishing to download the file can download the 8 chunks of 1 MB each from randomly chosen peers and with high probability recover the file. The issue with this system is that if a peer leaves the network and a new peer joins, that peer should not have to download all 8 MB to make a new coded 1 MB chunk for itself to store. So the question this paper answers is how much overhead (excess downloading) a new peer has to pay in order to store a coded packet, and how can we design codes whose overhead is low in terms of this metric so that peers can leave and join the network and still have the whole file stored. Alex calls these “regenerating codes,” which sounds kind of sci-fi to me.

• Code construction for two source interference (Elona Erez and Meir Feder, Tel Aviv University)

  This paper looked at non-multicast network coding, and was focused on coming up with decentralized and low-complexity algorithms for accomplishing this. The approach was to make a “quasiflow” and use a modified version of a multicommodity flow algorithm to construct the quasiflow.

• Characaterizations of network error correction/detection and erasure correction (Shenghao Yang and Raymond W. Yeung, The Chinese University of Hong Kong)

  This was a real big-picture talk, in which Prof. Yeung tried to argue that network coding has all the analogues of regular error correcting codes. In this sense, network coding is a generalization of algebraic coding. So there are analogies to the Singleton bound, and all sort of other things. In particular, minimum distance has a analogy in network coding, which can make a lot of intuitive connections clear.

The ITA Workshop was last week at UCSD, and as opposed to last year I decided to go down and attend. I had a good time, but it was a bit weird to be at a conference without presenting anything. It was worth it to get a snapshot of some of the things going on in information theory, and I got a few new ideas for problems that I should work on instead of blogging. But I find the exercise of blogging about the conference useful, and at least a few people have said some positive things about it. This time around I’m going to separate posts out by subject area, loosely. My attention and drive to attend talks decreased exponentially as the week progressed, more due to fatigue than anything else, so these posts may be short (a blessing for my friends who don’t care about information theory!) and more impressionistic at times.

One general gripe I had was that sessions were very de-synced from each other. Most session chairs were unable or unwilling to curtail speakers who went over, to the point where one session I attended finished after the break between sessions. I ended up missing a few talks I wanted to see because of this. I regard it as more of a failing on the part of the speaker — an experienced researcher with many conference talks under their belt should be know how to make a coherent 20 minute talk and not plan to run over. Dry runs can only tell you so much about timing, but one should be considerate towards the other speakers in the session and at the conference, no? I know this makes me sound a bit like a school-marm, but it bothers me to leave a talk before the theorem is presented so that I can make it to another talk.

I’ll write separately about the panel on publication issues, which raised some interesting points while dodging others. There was also a presentation by Dr. Sirin Tekinay, who is in charge of the NSF area under which information theory sits. I am woefully ignorant of the grant-writing process right now so I wasn’t sure how to take her comments, but it looks like a lot of emphasis is going to be on networks and cross-discipline work, as is the trend. Unfortunately, not all research can be said to have applications to networks, so that seems a bit unfortunate…

It should be up on ArXiV later today…

A.D. Sarwate and M. Gastpar
Deterministic list codes for state-constrained arbitrarily varying channels
Submitted to IEEE Transactions on Information Theory
ArXiV cs.IT/0701146

The capacity for the discrete memoryless arbitrarily varying channel (AVC) with cost constraints on the jammer is studied using deterministic list codes under both the maximal and average probability of error criteria. For a cost function $l(\cdot)$ on the state set and constraint $\Lambda$ on the jammer, the achievable rates are upper bounded by the random coding capacity $C_r(\Lambda)$. For maximal error, the rate $R = C_r(\Lambda) – \epsilon$ is achievable using list codes with list size $O(\epsilon^{-1})$. For average error, an integer $\lsym(\Lambda)$, called the \textit{symmetrizability}, is defined. It is shown that any rate below $C_r(\Lambda)$ is achievable under average error using list codes of list size $L > \lsym$. An example is given for a class of discrete additive AVCs.