Computer Science/Discrete Mathematics Seminar I

The INDEX problem is one of a handful of fundamental problems in communication complexity: Alice has an n-bit string x, Bob has an index k in [n], and the players wish to determine the k-th bit of x. It is easy to show that the problem is "hard" (requiring Omega(n) bits of communication) when messages only go from Alice to Bob, and is "easy" without this restriction. Can there be anything new to say about such a fundamental problem? Yes, provided one asks the right questions! In this talk, I shall show, roughly speaking, that in a successful INDEX protocol, either Alice must reveal Omega(n) information to Bob, or else Bob must reveal Omega(1) information to Alice, no matter what their communication pattern, and with "information" being measured w.r.t. an "easy" input distribution that fixes the protocol's Boolean output. Using the "information complexity paradigm", this somewhat technical result leads to tight data stream lower bounds on natural problems. To give one example, we show that recognizing Dyck languages is "hard" in the multi-pass streaming model, whereas it is "easy" in the bi-directional streaming model; this is the first natural separation between the models. I shall show most of the proof of this result in the talk, and hint at a few similar results, dealing with other languages. This is joint work with Cormode, Kondapally and McGregor.