Approximate Counting via Correlation Decay

Tuesday, March 17, 2015 - 11:20am - 12:00pm
Klaus 2443
Pinyan Lu (Microsoft Research)
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.