12 citations · 20 across the 4 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2010★ 3 cited
A Full Derandomization of Schoening's k-SAT Algorithm
Robin A. Moser, Dominik Scheder
Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running i…
cs.DS2010★ 12 cited
Using CSP To Improve Deterministic 3-SAT
Konstantin Kutzkov, Dominik Scheder
We show how one can use certain deterministic algorithms for higher-value constraint satisfaction problems (CSPs) to speed up deterministic local search for 3-SAT. This way, we imp…