12 citations · 20 across the 4 of their papers we have counts for
4 papers
PPZ For More Than Two Truth Values - An Algorithm for Constraint Satisfaction Problems
Dominik Scheder
We analyze the so-called ppz algorithm for (d,k)-CSP problems for general values of d (number of values a variable can take) and k (number of literals per constraint). To analyze i…
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…
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…
Using a Skewed Hamming Distance to Speed Up Deterministic Local Search
Dominik Scheder
Schoening presents a simple randomized algorithm for (d,k)-CSP problems with running time (d(k-1)/k)^n poly(n). Here, d is the number of colors, k is the size of the constraints, a…