### DIMACS Theoretical Computer Science Seminar

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.