Skip to content Skip to navigation
Computer Science Department Colloquium
2/16/2016 02:00 pm
Core A (Room 301)

Computational phase transitions meet statistical physics

Eric Vigoda, Georgia Tech

Faculty Host: Eric Allender

Abstract

This talk looks at randomly sampling from a huge collection of objects, and the associated approximate counting problems.  The type of sampling/counting problems we study arise in a variety of settings, for example, for inference in graphical models and reconstruction of phylogenetic trees.  We'll focus on combinatorial models where we can get a firm grasp on when these counting/sampling problems can be efficiently solved or when it is intractable even to obtain a rough estimate in the worst case.  We'll see a computational phase transition which occurs between efficiency and inapproximability. A beautiful connection arises: the critical point for this computational phase transition on general graphs is identical to the critical point for a classical statistical physics phase transition on infinite, regular trees.

Bio

Eric Vigoda received his PhD in CS from UC Berkeley in 1999. After postdoc stints at the University of Edinburgh and Weizmann Institute, Eric was a faculty member at the University of Chicago for 2002-4. Since 2004, Eric has been on the faculty at Georgia Tech. His work with M. Jerrum and A. Sinclair presenting a Markov Chain Monte Carlo (MCMC) algorithm for the permanent of a non-negative matrix won a Fulkerson Prize in 2006.