Algebraic proof systems over formulas.
From MaRDI portal
Recommendations
Cites work
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Complexity of Null- and Positivstellensatz proofs
- Complexity of Positivstellensatz proofs for the knapsack
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Eigenvalues and expanders
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- Exponential lower bounds for the pigeonhole principle
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1059248 (Why is no real title available?)
- scientific article; zbMATH DE number 2086404 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Lower bounds for polynomial calculus in the case of nonbinomial ideals.
- Lower bounds for the polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- On the sources of my book \textit{Moderne Algebra}
- Polynomial size proofs of the propositional pigeonhole principle
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Stable sets and polynomials
- The Positivstellensatz and Small Deduction Rules for Systems of Inequalities
- The relative efficiency of propositional proof systems
Cited in
(22)- Unsolvable systems of equations and proof complexity
- Several notes on the power of Gomory-Chvátal cuts
- Algebraic proofs over noncommutative formulas
- scientific article; zbMATH DE number 1059248 (Why is no real title available?)
- scientific article; zbMATH DE number 1114028 (Why is no real title available?)
- Characterizing propositional proofs as noncommutative formulas
- Proof Complexity Meets Algebra
- Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
- scientific article; zbMATH DE number 2086623 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- (Semi)Algebraic proofs over {±1} variables
- The power of the binary value principle
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Algebraic proofs over noncommutative formulas
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- First-order reasoning and efficient semi-algebraic proofs
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
- New lower bounds for polynomial calculus over non-Boolean bases
- Proving unsatisfiability with hitting formulas
- The power of the binary value principle
- A lower bound for polynomial calculus with extension rule
This page was built for publication: Algebraic proof systems over formulas.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401356)
