CS Events

Computer Science Department Colloquium

Computational phase transitions meet statistical physics


Download as iCal file

Tuesday, February 16, 2016, 02:00pm


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.

Speaker: Eric Vigoda


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 Geor

Location : Core A (Room 301)


Eric Allender

Event Type: Computer Science Department Colloquium



Georgia Tech