3 papers
cs.DS2022
Towards an Understanding of Long-Tailed Runtimes of SLS Algorithms
Jan-Hendrik Lorenz, Florian Wörz
The satisfiability problem is one of the most famous problems in computer science. Its NP-completeness has been used to argue that SAT is intractable. However, there have been trem…
cs.DS2021
Evidence for Long-Tails in SLS Algorithms
Florian Wörz, Jan-Hendrik Lorenz
Stochastic local search (SLS) is a successful paradigm for solving the satisfiability problem of propositional logic. A recent development in this area involves solving not the ori…
cs.AI2020
On the Effect of Learned Clauses on Stochastic Local Search
Jan-Hendrik Lorenz, Florian Wörz
There are two competing paradigms in successful SAT solvers: Conflict-driven clause learning (CDCL) and stochastic local search (SLS). CDCL uses systematic exploration of the searc…