Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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**: OAT S15/S16/S17

**Speaker**: Timon Hertli

Very recently Thurley [1] 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 [2]: 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 [3].

While this result is not necessary for [1], it might be useful for obtaining new approximation algorithms.

[1] Marc Thurley: An Approximation Algorithm for #k-SAT (arXiv, 2011)

[2] Mark R. Jerrum, Alistair Sinclair: Approximate counting, uniform generation and rapidly mixing markov chains (Information and Computation, 1989)

[3] Mark R. Jerrum, Leslie G. Valiant, Vijay V. Vazirani: Random generation of combinatorial structures from a uniform distribution (Theoretical Computer Science, 1986)

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login