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! We 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. We shall sketch a
proof of this result, and hint at other few similar results, dealing with 
other languages.