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

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

zbMATH Keywords

lower boundscommunication complexityzero-one programmingpropositional proof complexity

Mathematics Subject Classification ID

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 (19)

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

This page was built for publication: Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity