Polynomial calculus space and resolution width

DOI10.4086/TOC.2025.V021A006MaRDI QIDQ6860910zbMATH OpenFDO

Authors Nicola Galesi, Leszek Aleksander Kołodziejczyk, Neil Thapen

Publication date 10 February 2026

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4086/TOC.2025.V021A006

zbMATH Keywords

polynomial calculusproof complexityresolution

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A combinatorial characterization of resolution width
• A framework for space complexity in algebraic proof systems
• A generalized method for proving polynomial calculus degree lower bounds
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Approximate counting and NP search problems
• Exponential lower bounds for the pigeonhole principle
• From small space to small width in resolution
• Hard examples for resolution
• scientific article; zbMATH DE number 4145897 (Why is no real title available?)
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• Lower bounds for the polynomial calculus
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• On the automatizability of polynomial calculus
• Optimality of size-degree tradeoffs for polynomial calculus
• Optimality of size-width tradeoffs for resolution
• Perfect matching in random graphs is as hard as Tseitin
• Polynomial calculus space and resolution width
• Random resolution refutations
• Resolution lower bounds for the weak functional pigeonhole principle.
• Short proofs are narrow—resolution made simple
• Space bounds for resolution
• Space complexity in polynomial calculus
• Space Complexity in Propositional Calculus
• Space complexity of random formulae in resolution
• Supercritical space-width trade-offs for resolution
• The relative efficiency of propositional proof systems
• Tight lower bounds on the resolution complexity of perfect matching principles
• Total space in resolution
• Total space in resolution is at least width squared
• Towards an understanding of polynomial calculus: new separations and lower bounds

This page was built for publication: Polynomial calculus space and resolution width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6860910)