אירועים
אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב
עדי שרייבמן, מכון וייצמן למדע
יום ראשון, 20.01.2008, 11:00
חדר 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