Nie jesteś zalogowany |
A Full Derandomization of Schoening's k-SAT Algorithm
- Prelegent(ci)
- Dominik Scheder
- Afiliacja
- ETH Zurich
- Termin
- 31 marca 2011 12:15
- Pokój
- p. 5870
- Seminarium
- Seminarium "Algorytmika"
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 in time O(a^(n+o(n))).
Joint work with Robin A. Moser.
Joint work with Robin A. Moser.
