Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, July 28, 2011, 12:15 pm
Duration: 30 minutes
Location: ML J37.1
Speaker: Dominik Scheder
In 2010, Ryan Williams showed how to solve the satisfiability problem of ACC circuits in time 2^n / superpolynomial(n). Bjorklund showed that when one distills this algorithm down to CNF formulas, one obtains an algorithm whose running is in some way comparable to that of Schoening or PPSZ. Although being slower than these, it is an interesting algorithm, because it is very different from other SAT algorithms. In the talk, I will present this algorithm together with an analysis of its success probability and running time. The algorithm has not been published so far. I learned of this algorithm from Mohan Paturi, who is currently writing it up together with William Matthews and Daniel Lokshtanov.
Automatic MiSe System Software Version 1.4803M | admin login