Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Friday, November 16, 2012, 12:15 pm
Duration: 30 minutes
Location: HG D3.2
Speaker: Dominik Scheder (Aarhus University)
In 1998, Paturi, Pudlak, Saks, and Zane presented PPSZ, an elegant randomized algorithm for k-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on k-CNF formulas with n variables is at most 2(1 - εk)n, where εk = Ω(1/k). So far, no exponential lower bounds at all have been known. In this paper, we construct hard instances for PPSZ. That is, we construct satisfiable k-CNF formulas over n variables on which the expected running time is at least 2(1 - εk)n, for εk in O( log2(k) / k).
Automatic MiSe System Software Version 1.4803M | admin login