event

Correlation Decay and Deterministic Approximation Algorithms

Primary tabs

TITLE: Correlation Decay and Deterministic Approximation Algorithms SPEAKER: Dr. Prasad Tetali ABSTRACT: 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.

Status

  • Workflow Status: Published
  • Created By: Anita Race
  • Created: 10/12/2009
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016

Target Audience