You are not logged in | Log in

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.