Group:ACC Seminar
Title: Deterministic Local Search: Derandomizing Schoening's k-SAT Algorithm
Speaker: Domink Scheder
Time: 2011-10-21 13:30-2011-10-21 15:00
Venue: FIT 1-222

Abstract:
In 1999, Schoening presented a simple randomized algorithm for 3-SAT with running time 1.334^n. We give a deterministic version of this algorithm with almost the same running time.

Joint work with Robin Moser.



Short Bio: