Nie jesteś zalogowany | Zaloguj się

A Full Derandomization of Schoenings 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.