Approximate Counting via Correlation Decay

摘要

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. Based on this new approach, many new approximation schemes are obtained for counting problems on graphs, partition functions in statistical physics and so on.