Talks
Fall 2014
Approximate Counting via Correlation Decay
Wednesday, September 17th, 2014, 11:40 am–12:20 pm
Event:
Speaker:
Location:
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.
Attachment | Size |
---|---|
Approximate Counting via Correlation Decay (slides) | 436.94 KB |