Strong ETH holds for regular resolution

DOI10.1145/2488608.2488669MaRDI QIDQ5495819zbMATH OpenOpenAlexFDO

Authors Christopher Beck, Russell Impagliazzo

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsproof complexityquantum classical separationresolution

Mathematics Subject Classification ID

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

Recommendations

• Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
• Strong ETH and resolution via games and the multiplicity of strategies
• Strong ETH and resolution via games and the multiplicity of strategies
• Lower bounds for k-DNF resolution on random 3-CNFs
• Regular and General Resolution: An Improved Separation

Cited in

(8)

• Characterizing Tseitin-formulas with short regular resolution refutations
• Strong ETH and resolution via games and the multiplicity of strategies
• A separator theorem for hypergraphs and a CSP-SAT algorithm
• Super strong ETH is true for PPSZ with small resolution width
• An Introduction to Lower Bounds on Resolution Proof Systems
• Strong ETH and resolution via games and the multiplicity of strategies
• Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
• Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis

This page was built for publication: Strong ETH holds for regular resolution

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