Title: Disjointness is hard in the multi-party number-on-the-forehead
model
Speaker: Troy Lee, DIMACS
Abstract:
The disjointness function---determining if a number of sets share a
common element---is a notorious example in communication complexity of
a function which is hard, but it is hard to show it is hard.
Determining both the randomized and quantum communication complexity of
disjointness were longstanding open problems requiring innovative
techniques to solve.
The current disjointness frontier is the model of multiparty ``number-
on-the-forehead'' complexity, where player i knows the entire input x_
1, ..., x_k except for the string x_i on their forehead. This overlap
of information between players in this model makes showing lower bounds
especially challenging, but this challenge is rewarded by a wealth of
applications, for example to lower bounds on proof systems and a
general class of depth three circuits.
We show that disjointness requires randomized communication roughly n^
{1/2k} / 2^{2^{k-1}} in the general k-party number-on-the-forehead
model of complexity. The previous best lower bound was log n. To prove
our bound, we develop a new technique based on a vector norm induced by
cylinder intersections, a key concept in multiparty complexity which is
the generalization of combinatorial rectangles in the two party case.
By results of Beame, Pitassi, and Segerlind, our bounds imply 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).
Joint work with Adi Shraibman.