Algebraic proof systems over formulas.

DOI10.1016/S0304-3975(02)00446-2zbMath1044.68146MaRDI QIDQ1401356

Edward A. Hirsch, Dima Yu. Grigoriev

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Frege systemsAlgebraic propositional proof systems

Mathematics Subject Classification ID

Related Items (7)

Characterizing Propositional Proofs as Noncommutative Formulas ⋮ 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 ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ Several notes on the power of Gomory-Chvátal cuts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• Eigenvalues and expanders
• On the sources of my book \textit{Moderne Algebra}
• Lower bounds for the polynomial calculus
• Stable sets and polynomials
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Lower bounds for polynomial calculus in the case of nonbinomial ideals.
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Polynomial size proofs of the propositional pigeonhole principle
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The relative efficiency of propositional proof systems
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• The Positivstellensatz and Small Deduction Rules for Systems of Inequalities
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Complexity of Positivstellensatz proofs for the knapsack
• Complexity of Null- and Positivstellensatz proofs

This page was built for publication: Algebraic proof systems over formulas.