Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
DOI10.1016/J.IPL.2015.09.013zbMATH Open1346.68100DBLPjournals/ipl/BonacinaT16OpenAlexW2150412474WikidataQ61732565 ScholiaQ61732565MaRDI QIDQ894453FDOQ894453
Authors: Ilario Bonacina, Navid Talebanfard 
Publication date: 1 December 2015
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2015.09.013
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Cites Work
- On the complexity of \(k\)-SAT
- Short proofs are narrow—resolution made simple
- An improved exponential-time algorithm for k -SAT
- A characterization of tree-like resolution size
- On converting CNF to DNF
- Title not available (Why is that?)
- Strong ETH holds for regular resolution
- Exponential lower bounds for the PPSZ \(k\)-SAT algorithm
Cited In (7)
- Strong ETH and resolution via games and the multiplicity of strategies
- Title not available (Why is that?)
- Strong ETH holds for regular resolution
- On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
- Conditional lower bounds for failed literals and related techniques
- Strong ETH and resolution via games and the multiplicity of strategies
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
This page was built for publication: Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894453)
