5 papers
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…
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…
Statistical privacy-preserving message dissemination for peer-to-peer networks
David Mödinger, Jan-Hendrik Lorenz, Fanz J. Hauck
Concerns for the privacy of communication is widely discussed in research and overall society. For the public financial infrastructure of blockchains, this discussion encompasses t…
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…
The Potential of Restarts for ProbSAT
Jan-Hendrik Lorenz, Julian Nickerl
This work analyses the potential of restarts for probSAT, a quite successful algorithm for k-SAT, by estimating its runtime distributions on random 3-SAT instances that are close t…