דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Disjointness is hard in the multi-party number-on-the-forehead model
event speaker icon
עדי שרייבמן, מכון וייצמן למדע
event date icon
יום ראשון, 20.1.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We show that disjointness requires randomized communication Omega(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((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 = loglog n -O(logloglog n).

Joint work with Troy Lee from Rutgers University
[בחזרה לאינדקס האירועים]