Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 15, 2011, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Timon Hertli
Very recently Thurley  gave a randomized algorithm that approximates the number of satisfying assignments of a k-CNF. The running time is still exponential, but considerably faster than the fastest known algorithms counting exactly.
I will present a classical result by Jerrum and Sinclair : If we can approximate the number of satisfying assignments up to a factor of poly(n), we can also do so up to (1+1/poly(n)). This holds more generally for so-called self-reducible problems. The result combines rapidly mixing markov chains with a reduction from approximate counting to almost uniform generation by Jerrum, Valiant and Vazirani .
While this result is not necessary for , it might be useful for obtaining new approximation algorithms.
 Marc Thurley: An Approximation Algorithm for #k-SAT (arXiv, 2011)
 Mark R. Jerrum, Alistair Sinclair: Approximate counting, uniform generation and rapidly mixing markov chains (Information and Computation, 1989)
 Mark R. Jerrum, Leslie G. Valiant, Vijay V. Vazirani: Random generation of combinatorial structures from a uniform distribution (Theoretical Computer Science, 1986)
Automatic MiSe System Software Version 1.4803M | admin login