Abstract | ||
---|---|---|
Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time an * poly(n) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time an+o(n). |
Year | DOI | Venue |
---|---|---|
2011 | 10.1145/1993636.1993670 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
full derandomization,deterministic version,k-sat algorithm,simple randomized algorithm,sat,deterministic | Conference | abs/1008.4067 |
ISSN | Citations | PageRank |
0737-8017 | 27 | 1.09 |
References | Authors | |
12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Robin A. Moser | 1 | 240 | 12.51 |
Dominik Scheder | 2 | 85 | 13.54 |