Linear gaps between degrees for the polynomial calculus modulo distinct primes

DOI10.1006/jcss.2000.1726zbMath1007.03052MaRDI 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 bounds; satisfiability; Gröbner basis algorithm; minimum degree of polynomial calculus refutations; mod \(p\) counting principle; Tseitin's graph tautologies

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03F20: Complexity of proofs

Related Items

Proof Complexity Meets Algebra, The Complexity of Propositional Proofs, Complexity of Null- and Positivstellensatz proofs, Towards NP-P via proof complexity and search, Algebraic proofs over noncommutative formulas, Resolution over linear equations and multilinear proofs, Algebraic proof systems over formulas., Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, The complexity of the Hajós calculus for planar graphs, Efficient algorithms for privately releasing marginals via convex relaxations, Several notes on the power of Gomory-Chvátal cuts, Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies, A Framework for Space Complexity in Algebraic Proof Systems, Space Complexity in Polynomial Calculus, Limitations of Algebraic Approaches to Graph Isomorphism Testing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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