On separating nondeterminism and randomization in communication complexity
Ravi Kumar
Yahoo! Research

In the two-party communication complexity model, we show that the
tribes function on n inputs has two-sided error randomized complexity
Omega(n), while its nondeterminstic complexity and co-nondeterministic
complexity are both Theta(sqrt(n)).  This separation between
randomized and nondeterministic complexity is the best possible and it
settles an open problem posed by Beame--Lawry and Kushilevitz--Nisan.

Our lower bound is obtained using generalizations of information
complexity, which quantifies the minimum amount of information that
will have to be revealed about the inputs by every correct
communication protocol.

(Joint work with T. S. Jayram and D. Sivakumar)