Fall 2014

Approximate Counting via Correlation Decay

Wednesday, September 17th, 2014 11:40 am12:20 pm

Add to Calendar


Calvin Lab Auditorium

In this talk, I will survey some recent development of approximate counting algorithms based on correlation decay technique. Unlike the previous major approximate counting approach based on sampling such as Markov Chain Monte Carlo (MCMC), correlation decay based approach can give deterministic fully polynomial-time approximation scheme (FPTAS) for a number of counting problems. At the heart of this approach is to prove that certain mapping derived from a local recursion is contractive under some local Riemann metric.