Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 30, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Robin Moser
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+epsilon)^n * poly(n)), where epsilon > 0 can be made arbitrarily small.
Joint work with Dominik Scheder.
Automatic MiSe System Software Version 1.4803M | admin login