The surprising power of constant depth algebraic proofs

DOI10.1145/3373718.3394754MaRDI QIDQ5145666zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Complexity of proofs (03F20)

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

Cited in

(12)

• Regular resolution effectively simulates resolution
• Semialgebraic proofs, IPS lower bounds, and the -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
• New lower bounds for polynomial calculus over non-Boolean bases
• The power of the binary value principle
• 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)