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

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: