Name
Title | ||
|---|---|---|
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity |
Abstract | ||
|---|---|---|
We prove that an $\omega(\log^4 n)$ lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an $n^{\omega(1)}$ size lower bound for treelike Lovász-Schrijver systems that refute unsatisfiable formulas in conjunctive normal form (CNFs). More generally, we prove that an $n^{\Omega(1)}$ lower bound for the $(k+1)$-party NOF communication complexity of set disjointness implies a $2^{n^{\Omega(1)}}$ size lower bound for all treelike proof systems whose formulas are degree $k$ polynomial inequalities. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/060654645 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
multiparty communication complexity,set disjointness,three-party number-on-the-forehead,sz-schrijver systems,party nof communication complexity,polynomial inequality,sz-schrijver system,lower bounds,set-disjointness function,treelike lov,communication complexity,conjunctive normal form,treelike proof system,lower bound | Journal | 37 |
Issue | ISSN | ISBN |
3 | 0097-5397 | 3-540-27580-0 |
Citations | PageRank | References |
27 | 0.84 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Toniann Pitassi | 2 | 2282 | 155.18 |
| Nathan Segerlind | 3 | 223 | 11.22 |