Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 19, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Dominik Scheder
The currently fastest deterministic algorithm for k-SAT is based on deterministic local search, introduced by Dantsin et al. (2002). Basically the same algorithm can also be used to solve (d,k)-CSPs (constraint satisfaction problems), which are the same as CNF formulas, but with d instead of 2 'truth values'. In the talk, I will present this algorithm and show a surprisingly simple way to substantially improve its running time.
Automatic MiSe System Software Version 1.4803M | admin login