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.

---