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.