All reports by Author Adi Shraibman:

__
TR08-003
| 25th December 2007
__

Troy Lee, Adi Shraibman#### Disjointness is hard in the multi-party number-on-the-forehead model

Troy Lee, Adi Shraibman

We show that disjointness requires randomized communication

Omega(\frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}})

in the general k-party number-on-the-forehead model of complexity.

The previous best lower bound was Omega(\frac{log n}{k-1}). By

results of Beame, Pitassi, and Segerlind, this implies

2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver

proof systems needed to refute certain unsatisfiable ...
more >>>