Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

DOI10.1137/060654645zbMath1148.68023MaRDI QIDQ3507523

Nathan Segerlind, Toniann Pitassi, P. W. Beame

Publication date: 19 June 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060654645

zbMATH Keywords

lower bounds; communication complexity; zero-one programming; propositional proof complexity

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C09: Boolean programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03F20: Complexity of proofs

Related Items

Unnamed Item, Communication Lower Bounds via Critical Block Sensitivity, Unnamed Item, Unnamed Item, Unnamed Item, Reflections on Proof Complexity and Counting Principles, Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols, Adventures in monotone complexity and TFNP, Narrow Proofs May Be Maximally Long, Towards NP-P via proof complexity and search, The NOF multiparty communication complexity of composed functions, One-way multiparty communication lower bound for pointer jumping with applications, Tight size-degree bounds for sums-of-squares proofs, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, Resolution over linear equations modulo two, Dag-like communication and its applications, The Multiparty Communication Complexity of Set Disjointness, On the Non-deterministic Communication Complexity of Regular Languages, ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES