Campus Event Calendar
Event Entry
What and Who
A Full Derandomization of Schoening's k-SAT Algorithm
Dominik Scheder
ETH Zürich
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 5 October 2010
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Schoening in 1999 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.
Contact
Reto Spöhel
--email hidden
passcode not visible
logged in users only
Reto Spöhel, 09/01/2010 11:40 -- Created document.