Recent News
Inaugural School of Engineering Teaching Innovation Fellows selected
February 2, 2024
UNM computer scientist wins NSF CAREER Award to optimize supercomputer performance
February 1, 2024
Hand and Machine Lab’s Experimental Clay Exhibition closing celebration Nov. 17
November 15, 2023
Moses selected as special assistant to the dean for educational initiatives
October 3, 2023
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.