A Full Derandomization of Schoening's k-SAT Algorithm

Speaker(s)

Dominik Scheder

Affiliation

ETH Zurich

Date

March 31, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---