Optimality of size-degree tradeoffs for polynomial calculus
From MaRDI portal
Publication:2946621
DOI10.1145/1838552.1838556zbMath1352.03066OpenAlexW2076972272MaRDI QIDQ2946621
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
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