You are not logged in |
A Full Derandomization of Schoenings 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.
