A Little Advice can be Very Helpful



Faith Ellen

Monday, April 30, 2012
4:00 PM,
5130 Upson Hall



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.