The surprising power of constant depth algebraic proofs
From MaRDI portal
(Redirected from Publication:5145666)
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
(14)- Another look at degree lower bounds for polynomial calculus
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Some subsystems of constant-depth Frege with parity
- Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
- Proof complexity meets algebra
- (Semi)Algebraic proofs over {±1} variables
- Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
- Proof complexity lower bounds from algebraic circuit complexity
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Regular resolution effectively simulates resolution
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- New lower bounds for polynomial calculus over non-Boolean bases
- The power of the binary value principle
- A lower bound for polynomial calculus with extension rule
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)
