Distributed Beam-forming: New Preprint

Besides NSF proposals, another item that took up time over my winter non-break was finishing a submission to ISIT 2008. To me, this paper was another example of how CS theory people and EE theory people are often tackling the same sort of problems, just in a different language.

The paper is titled Distributed Beamforming with Binary Signaling. Here's the English version of the problem. A bunch of weak transmitters are trying to transmit the same message to a receiver. Before sending the message, they are all out of phase, so their signals potentially cancel each other. They'd like to send so that they are all mostly in phase, so the signals reinforce each other and the message gets through. Initially, nobody knows their phase. The only communication possible is all the transmitters can send a signal, and the receiver can broadcast information back. How quickly can alignment occur?

To better understand the problem, we simplified it as follows. In each round, each transmitter can send a bit, a -1 or +1. Suppose the jth transmitter send the bit b(i,j) in the ith round. The jth transmitter has, for all time, a fixed phase p(j), which is +1 or -1. The receiver's obtained signal in the ith round is |sum_j b(i,j)p(j)|. If there are n transmitters, we'd like to get the obtained signal to beta n for some constant 0 < beta < 1 as quickly as possible; this is what we'll mean by alignment. The system is fully distributed, so transmitters can't communicate directly, and the only feedback they get is 1 bit broadcast every round. In this simple model, we looked at lower bounds and algorithms. The lower and upper bounds are both linear in n, but trying to get those constant factors right is apparently pretty important.

While this is a natural EE theory-type problem, it feels close to very similar problems in communication complexity, at least when simplified in this way. It was also interesting working on a lower bound, where we developed a reduction from a standard rate distortion problem. It seems to me EE people don't generally think in terms of reductions, at least not the way CS people do, although it's a terminology and framework that I think is increasing in use at conferences like ISIT. On the other hand, CS people don't always do reductions that give specific constant factors (in this case, related to entropy). So all in all it was an interesting reduction to develop here.

The "full paper" (ISIT papers are limited to 5 pages) will cover a lot more variations and have more details, though I expect there will still be many open problems. More generally, the theme of unifying the "communication complexity" picture between EE and CS, much as the coding theory picture has been greatly unified of late, seems like a great place to look for research problems.

Update from ISIT 2

The winner of the Claude E. Shannon Award, given by the IEEE Information Theory Society for "profound and consistent contributions to information theory", went to Sergio Verdu from Princeton. He is the youngest person to win the award (he is under 50). Apparently, all previous winners are now over 65. As the award recipient, he gave this year's Shannon lecture. His lecture went into ways he likes to teach information theory and relationships to his research. From my standpoint, he talked about various formulas and bounds and how to interpret them; with the right interpretation, the results become simple, and moreover, armed with the insight from finding the right interpretation, you are led to new results and generalizations. Another key point in this mix was the relationship between bounds for fixed length sequences and asymptotic bounds, and how the right interpretations make the connections between the two more transparent. I found it a very interesting talk, although I have to admit, my lack of facility with information-theoretic notation means I missed a lot that would have been nice to get. (The talk went over a lot, fast. I suppose I should teach information theory at some point so that I'll understand it better, and then listen to the talk again.) I highly recommend the talk, especially to those interested in coding/compression/entropy; I'm sure the slides/video will be appearing online shortly.

My student Adam Kirsch gave a talk about a paper with my former student Eleni Drinea on an information theoretic and improved approach to lower bounds on the deletion channel.

I gave a talk on upper bounds for the deletion channel.

I promise to return to the question of "interesting open questions in network coding", preferably with a guest blogger or bloggers more expert than I, in the near future.

After ISIT, I flew into London, where I'm giving a (networking) talk at UCL, hosted by Brad Karp (no relation to Dick Karp), and a group of us went out to fantastic London dinner. (I promised Brad I'd put the fantastic dinner part in the blog.)

Update from ISIT

I have been hanging out mostly at the network coding sessions. For those who haven't seen the term, the one sentence description of network coding is that you combine routing with coding -- intermediate nodes do not just store and forward, they get to evaluate functions of received packets and send those on as needed. Why aren't there more CS theory people working on network coding (myself included!)? It's a huge relatively new area in information theory and networking. There are lots of interesting, challenging open problems. Lots more info here. Also, there's a Scientific American article this month by three of the leaders in the field -- Michelle Effros, Ralf Koetter, and Muriel Medard (three top names in information theory that CS people should become familiar with if they are not...) -- that gives excellent high-level background.

The most interesting talk so far was the work by Koetter and Kschischang, which reduces network coding with erasure and errors to an interesting coding variant. In this setting, codewords are vector subspaces; erasures delete a basis vector from the subspace and errors add a spurious basis vector to the subspace. What do codes in this world look like? (Hopefully I'm doing the question some justice -- it was a great talk.)

Michael Luby and Amin Shokrollahi won the IEEE Eric E. Sumner Award "For bridging mathematics, internet design, and mobile broadcasting as well as successful standardization." Go Digital Fountain.

I gave a talk on good codes for limited insertion/deletion channels.

At the lunch, I talked with some people about how the information theory community doesn't really have a "competitive" conference -- like a FOCS/STOC, or a SIGCOMM. They were wondering about how to and the impact of adding one. I suggested adding special single-track sessions (as opposed to the eight parallel sessions) for the key papers to ISIT.