Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 24, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Timon Hertli
We present a zero-error randomized algorithm for #k-SAT by Impagliazzo, Matthews, and Paturi . The algorithm is a corollary to a more general algorithm for bounded depth circuits based on Håstad's switching lemma.
Noteworthy is that this algorithm is much faster (for large k) than the best known determinstic algorithm. The randomized algorithm runs in 2(1-1/(30k))n, whereas the deterministic algorithm takes time approximately 2(1-1/(2^k))n (n denotes the number of variables).
 Russell Impagliazzo, William Matthews, and Ramamohan Paturi: A Satisfiability Algorithm for AC0 (SODA, 2012)
Automatic MiSe System Software Version 1.4803M | admin login