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.

I had meant to start blogging ISIT as it was going on, but that turned out to be infeasible due to a number of factors. The most relevant was that I spent the first 3 days of this year’s conference battling a fever, so by the time I got back to the hotel I was in no mood to type up any of the notes I had taken from the talks, and I also had to leave early the first two days so that I could lie down. Another downside was that my attention was not as sharp as it should have been, so I apologize in advance for the facile nature of my observations.

In general, the program this year felt way more Shannon-theory heavy to me than last year’s. Perhaps that’s because I wasn’t hanging out with many coding theorists, so I didn’t hear about the talks, but I felt like the coding talks in which I was interested were few in number. Furthermore, I ended up missing the one or two that I really wanted to attend (such as the new Reed-Solomon list decoding algorithm).

My biggest gripe was the lack of water at the sessions — there were two snack breaks, between the two morning and two afternoon sessions. There was juice, water, coffee and caffeinated tea, and everything was cleared out immediately upon the resumption of the sessions. I understand taking away the coffee and juice, but there was no water to be had in the session rooms and none in the convention area unless you bought it at the overpriced bar. Perhaps that’s in the contract with the convention center, but it’s a lousy deal.

This year they were also quite zealous in checking that everyone had their conference badge to prove that they had registered. The stinginess with respect to the water complemented (in some sense) their concern that freeloaders not be allowed into the sessions. I left my badge at the hotel one day and was made to get a temporary one for that day.

The big news of course was that Bob Gray won the Shannon Award for next year, which made me happy. I heard some people say beforehand that he seemed like an outside shot since he’s not a pure information theorist per se, and that’s what the award is about. In some sense Sergio Verdú is an Information Theorist’s information theorist, and I think one would be hard-pressed to find a candidate like him. You wouldn’t say Kailath is a pure IT guy either, right?

All in all, I had a good time, and had a few interesting research discussions with different people. I find myself wanting to work on some new problems, which is good from the perspective of learning some new areas, but bad from the perspective of trying to wrap things up and write my thesis. I was asked by several people if I was graduating soon and what I was planning on doing next, which is always a terrifying question. Hopefully I’ll get some of that sorted out this summer…