News Archives

[Colloquium] Phase Transitions In Approximate Counting

September 18, 2014

Watch Colloquium:

MOV FILE

  • Date: Thursday, September 18, 2014
  • Time: 11:00 -- 12:15 PM
  • Place: Dane Smith Hall 125


Speaker: Eric Vigoda,
College of Computing,
Georgia Tech

Abstract: This talk will give an overview of recent results establishing connections between the complexity of approximate counting problems and phase transitions in statistical physics. I will focus on recent work (with A. Galanis and D. Stefankovic in STOC '14) showing hardness results for approximately counting colorings. The key tool is a simplified approach for the analysis of spin systems on random regular graphs.

Bio: Eric Vigoda is a Professor of Computer Science at the Georgia Institute of Technology. He received his PhD from UC Berkeley in 1999. He was a faculty member at the University of Chicago from 2002-2004, and then moved to Georgia Tech in 2004. He was awarded a Fulkerson prize in 2006 (with A. Sinclair and M. Jerrum) for their work on approximating the permanent of a non-negative matrix.