Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-003 | 25th December 2007 00:00

Disjointness is hard in the multi-party number-on-the-forehead model

RSS-Feed




TR08-003
Authors: Troy Lee, Adi Shraibman
Publication: 18th January 2008 13:02
Downloads: 2877
Keywords: 


Abstract:

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 CNFs, and
super-polynomial lower bounds on the size of any tree-like proof system
whose terms are degree-d polynomial inequalities for
d = log log n - O(log log log n).

To prove our bound, we develop a new technique for showing lower bounds in the number-on-the-forehead model which
is based on the norm induced by cylinder intersections. This bound
naturally extends the linear program bound for rank useful in the
two-party case to the case of more than two parties, where the
fundamental concept of monochromatic rectangles is replaced by
monochromatic cylinder intersections. Previously, the only general
method known for showing lower bounds in the unrestricted
number-on-the-forehead model was the discrepancy method, which can
only show bounds of size O(log n) for disjointness.

To analyze the bound given by our new technique for the disjointness
function, we extend an elegant framework developed by Sherstov in the two-party case which relates polynomial degree to communication
complexity. Using this framework we are able to obtain bounds for any
tensor of the form F(x_1,\ldots,x_k) = f(x_1 \wedge \ldots \wedge x_k)
where f is a function which only depends on the number of ones in the
input.



ISSN 1433-8092 | Imprint