Linear gaps between degrees for the polynomial calculus modulo distinct primes

DOI10.1006/jcss.2000.1726zbMath1007.03052OpenAlexW2098642112MaRDI QIDQ5943090

Toniann Pitassi, Dima Yu. Grigoriev, Russell Impagliazzo, Samuel R. Buss

Publication date: 24 March 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1726

zbMATH Keywords

lower boundssatisfiabilityGröbner basis algorithmminimum degree of polynomial calculus refutationsmod \(p\) counting principleTseitin's graph tautologies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (23)

Limitations of Algebraic Approaches to Graph Isomorphism Testing ⋮ Space Complexity in Polynomial Calculus ⋮ Sharp Effective Finite-Field Nullstellensatz ⋮ Towards NP-P via proof complexity and search ⋮ Algebraic proof systems over formulas. ⋮ 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 ⋮ Resolution over linear equations and multilinear proofs ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ The complexity of the Hajós calculus for planar graphs ⋮ Several notes on the power of Gomory-Chvátal cuts ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies ⋮ Unnamed Item ⋮ The Complexity of Propositional Proofs ⋮ Resolution with counting: dag-like lower bounds and different moduli ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Propositional proof complexity ⋮ Adventures in monotone complexity and TFNP ⋮ Efficient algorithms for privately releasing marginals via convex relaxations ⋮ Reflections on Proof Complexity and Counting Principles

Cites Work

• Random CNF's are hard for the polynomial calculus
• Good degree bounds on Nullstellensatz refutations of the induction principle
• Lower bounds for the polynomial calculus
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Space complexity in propositional calculus
• Hard examples for resolution
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On the degree of ideal membership proofs from uniform families of polynomials over a finite field
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear gaps between degrees for the polynomial calculus modulo distinct primes