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.