Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
From MaRDI portal
Publication:3507523
DOI10.1137/060654645zbMath1148.68023OpenAlexW1992641578MaRDI 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
Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Narrow Proofs May Be Maximally Long, Communication Lower Bounds via Critical Block Sensitivity, Dag-like communication and its applications, Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols, Tight size-degree bounds for sums-of-squares proofs, Towards NP-P via proof complexity and search, Unnamed Item, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, On the Non-deterministic Communication Complexity of Regular Languages, The NOF multiparty communication complexity of composed functions, One-way multiparty communication lower bound for pointer jumping with applications, ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES, Unnamed Item, The Multiparty Communication Complexity of Set Disjointness, Adventures in monotone complexity and TFNP, Unnamed Item, Unnamed Item, Resolution over linear equations modulo two, Reflections on Proof Complexity and Counting Principles
