Exponential Lower Bounds for the PPSZ k-SAT Algorithm

DOI10.1137/1.9781611973105.91zbMath1421.68058OpenAlexW4244939413MaRDI QIDQ5741800

Shiteng Chen, Navid Talebanfard, Bang-Sheng Tang, Dominik Scheder

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.91

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (3)

Strong ETH and resolution via games and the multiplicity of strategies ⋮ Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis ⋮ Super strong ETH is true for PPSZ with small resolution width

This page was built for publication: Exponential Lower Bounds for the PPSZ k-SAT Algorithm