Correlation Decay and Deterministic Approximation Algorithms
- Series
- ACO Student Seminar
- Time
- Tuesday, September 23, 2008 - 15:00 for 1 hour (actually 50 minutes)
- Location
- ISyE executive classroom
- Speaker
- Prasad Tetali – School of Mathematics, Georgia Tech
The notion of a correlation decay, originating in statistical physics, has recently played an important role in yielding deterministic approximation algorithms for various counting problems. I will try to illustrate this technique with two examples: counting matchings in bounded degree graphs, and counting independent sets in certain subclasses of claw-free graphs.