Super strong ETH is true for PPSZ with small resolution width

DOI10.4230/LIPIcs.CCC.2020.3OpenAlexW3046491176MaRDI QIDQ5092450

Navid Talebanfard, Dominik Scheder

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12555/pdf/LIPIcs-CCC-2020-3.pdf/

zbMATH Keywords

resolution\(k\)-SATPPSZ

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite common coverings of pairs of regular graphs
• On super strong ETH
• A combinatorial characterization of resolution width
• An improved exponential-time algorithm for k -SAT
• PPSZ for k ≥ 5: More Is Better
• Faster k -SAT algorithms using biased-PPSZ
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
• Exponential Lower Bounds for the PPSZ k-SAT Algorithm

This page was built for publication: Super strong ETH is true for PPSZ with small resolution width