Optimality of size-degree tradeoffs for polynomial calculus

DOI10.1145/1838552.1838556zbMath1352.03066OpenAlexW2076972272MaRDI QIDQ2946621

Massimo Lauria, Nicola Galesi

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1838552.1838556

zbMATH Keywords

computational complexitypolynomial calculusproof complexityalgebraic proofs

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)

Related Items

A note about \(k\)-DNF resolution ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ On the automatizability of polynomial calculus ⋮ Automatizability and Simple Stochastic Games ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Sum of squares bounds for the ordering principle ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Another look at degree lower bounds for polynomial calculus ⋮ On Linear Resolution