Proof complexity meets algebra

DOI10.4230/LIPICS.ICALP.2017.110zbMATH Open1442.03031OpenAlexW2963245542MaRDI QIDQ5111442FDOQ5111442

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/

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

zbMATH Keywords

proof complexityreductionsconstraint satisfaction problemgap theorems

Mathematics Subject Classification ID

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

Cited In (6)

• Proof Complexity Meets Algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Title not available (Why is that?)
• Complexity of Semialgebraic Proofs with Restricted Degree of Falsity

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)