Title: Disjointness is hard in the multi-party number-on-the-forehead model
Speaker: Troy Lee
Date: Wednesday, January 30, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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 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.