(Semi)Algebraic proofs over {±1} variables

DOI10.1145/3357713.3384288MaRDI QIDQ5144899zbMATH OpenOpenAlexFDO

Authors

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3357713.3384288

zbMATH Keywords

lower boundspolynomial calculusproof complexityrandom formulassum-of-squares

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The surprising power of constant depth algebraic proofs
• Lower bounds for the polynomial calculus
• Algebraic proof systems over formulas.
• scientific article; zbMATH DE number 1916823
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Cited in

(8)

• Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Polynomial calculus for optimization
• New lower bounds for polynomial calculus over non-Boolean bases
• Lower bounds for regular resolution over parities
• A lower bound for polynomial calculus with extension rule
• On the degree automatability of sum-of-squares proofs
• Searching for falsified clause in random ( n)-CNFs is hard for randomized communication

This page was built for publication: (Semi)Algebraic proofs over {±1} variables

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