A Little Advice can be Very Helpful

**Faith Ellen**

**
**

**M****onday, April 30, 2012**

4:00 PM,
5130 Upson Hall

__Abstract:__

Patrascu recently introduced a number-on-the-forehead communication
model in which one player only participates by sending advice
to a second player at the beginning of the protocol. He gave reductions

from the problem of solving an asymmetric version of set-disjointness in
this model to a diverse collection of natural dynamic data structure
problems in the cell probe model. He also conjectured that, for any hard

problem in the standard two party communication model, the asymmetric
version of the problem is hard in his model.

This talk will present several surprising results about Patrascu's model,
including a simple, deterministic protocol for the asymmetric
version of equality with $O(\log n)$ communication complexity
and a deterministic protocol for the asymmetric version of the set
disjointness problem with $O(\sqrt{n})$ communication complexity.
(In the two party communication model, equality has large deterministic
communication complexity and set disjointness has large randomized
communication complexity.) The randomized and deterministic communication
complexities of problems in Patrascu's model will also be shown to
differ by no more than a multiplicative factor of $O(\log n)$.

This work is joint with Arkadev Chattopadhyay, Jeff Edmonds,
and Toni Pitassi and appeared at SODA 2012.