I have gathered my conference blogging into a single page, linked on the sidebar. Assuming I have the bandwidth, I’ll blog a bit about SSP 2007 and ITW 2007, and “Global Conversations: A Festival of Marginalized Languages,” which I will be attending in Irvine this fall.

# Daily Archives: July 15, 2007

# ISIT 2007 : the plenaries

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.

# ISIT 2007 : multi-user IT and cognitive radio

**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.

# ISIT 2007 : security, wiretapping, and jamming

**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.