Proof complexity meets algebra

DOI10.4230/LIPICS.ICALP.2017.110MaRDI QIDQ5111442zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Joanna Ochremiak

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7495/pdf/LIPIcs-ICALP-2017-110.pdf/

zbMATH Keywords

constraint satisfaction problemgap theoremsproof complexityreductions

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational aspects of satisfiability (68R07)

Recommendations

• Proof Complexity Meets Algebra
• scientific article; zbMATH DE number 1916823
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• scientific article; zbMATH DE number 2086404
• The surprising power of constant depth algebraic proofs

Cited in

(6)

• Proof Complexity Meets Algebra
• scientific article; zbMATH DE number 2086404 (Why is no real title available?)
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
• scientific article; zbMATH DE number 7753415 (Why is no real title available?)
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

This page was built for publication: Proof complexity meets algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111442)