Name
Title | ||
|---|---|---|
Lower Bounds for Lov[a-acute]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.( 1) size lower bound for treelike Lovasz - 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 |
|---|---|---|
2007 | 10.1137/060654645 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
propositional proof complexity,zero-one programming,communication complexity,lower bounds | Journal | 37 |
Issue | ISSN | Citations |
3 | 0097-5397 | 7 |
PageRank | References | Authors |
0.47 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Toniann Pitassi | 2 | 2282 | 155.18 |
| Nathan Segerlind | 3 | 223 | 11.22 |