The surprising power of constant depth algebraic proofs

DOI10.1145/3373718.3394754zbMATH Open1498.03151OpenAlexW3028950990MaRDI QIDQ5145666FDOQ5145666

Authors: Russell Impagliazzo, Sasank Mouli, Toniann Pitassi 

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

Recommendations

• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• The strength of multilinear proofs
• Some subsystems of constant-depth Frege with parity
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
• Lower bounds for the polynomial calculus

zbMATH Keywords

proof complexitybounded depthpolynomial calculusalgebraic proofs\(\mathrm{AC}^0[\mathrm{p}\)-Frege]

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cited In (10)

• Regular resolution effectively simulates resolution
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• Proof complexity lower bounds from algebraic circuit complexity
• Proof complexity meets algebra
• Some subsystems of constant-depth Frege with parity
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
• Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Another look at degree lower bounds for polynomial calculus
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs

This page was built for publication: The surprising power of constant depth algebraic proofs

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