Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
From MaRDI portal
Publication:5326581
DOI10.1007/978-3-642-39206-1_37zbMath1336.03065OpenAlexW1505776303WikidataQ61732585 ScholiaQ61732585MaRDI QIDQ5326581
Marc Vinyals, Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström
Publication date: 6 August 2013
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-39206-1_37
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (11)
From Small Space to Small Width in Resolution ⋮ Narrow Proofs May Be Maximally Long ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Space Complexity in Polynomial Calculus ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ On semantic cutting planes with very small coefficients ⋮ Space proof complexity for random 3-CNFs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Total Space in Resolution ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
