# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Tuesday, November 15, 2011, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G51

**Speaker**: Timon Hertli

## Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

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: 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