CS Events

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.