Lower bounds for the polynomial calculus and the Gröbner basis algorithm
From MaRDI portal
Publication:1961057
DOI10.1007/s000370050024zbMath0946.68129OpenAlexW2056382067MaRDI QIDQ1961057
Jiří Sgall, Russell Impagliazzo, Pavel Pudlák
Publication date: 30 March 2000
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s000370050024
Related Items
Narrow Proofs May Be Maximally Long ⋮ Unnamed Item ⋮ Exploring the vacuum geometry of \(\mathcal N=1\) gauge theories ⋮ Space Complexity in Polynomial Calculus ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Towards NP-P via proof complexity and search ⋮ Algebraic proof systems over formulas. ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ Algebraic proofs over noncommutative formulas ⋮ On the automatizability of polynomial calculus ⋮ Proof Complexity Meets Algebra ⋮ Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ Unnamed Item ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz ⋮ On the complexity of Hilbert refutations for partition ⋮ Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity ⋮ Linear gaps between degrees for the polynomial calculus modulo distinct primes ⋮ The Complexity of Propositional Proofs ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Sum of squares bounds for the ordering principle ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Unnamed Item ⋮ Another look at degree lower bounds for polynomial calculus ⋮ Resolution over linear equations modulo two
