### DIMACS Working Group on Current Topics in Markov Chains and Phase Transitions

#### March 26 - 30, 2007

Georgia Institute of Technolgy

**Organizers:**
** Dana Randall**, Georgia Institute of Technolgy, randall@cc.gatech.edu
**Eric Vigoda**, Georgia Institute of Technolgy, vigoda@cc.gatech.edu

Presented under the auspices of the Special Focus on Discrete Random Systems.

Many local Markov chains based on local dynamics are known to undergo
a phase transition as a parameter λ of the system is varied. For example,
in the context of independent sets, the Gibbs distribution assigns each
independent set a weight
λ|I|, and a natural Markov chain adds or deletes a single vertex at
each step. It is believed that there is a critical point λ_{c}
such that for λ < λ_{c}, local dynamics converge in polynomial time
while for λ > λ_{c} they require exponential time. A parallel phenomenon
arises in statistical physics in the context of determining whether there is a unique
limiting distribution (e.g., for independent sets) on the infinite lattice, known as a Gibbs
state. While there has been progress in making such observations rigorous, many recent
results have been the direct or indirect outcome of interdisciplinary collaboration, building
on insights from both disciplines.

This working group will promote more collaborations by bringing
together researchers from
computer science, combinatorics, probability, and mathematical physics
to study topics central to
the interplay between
work on Markov chains and on phase transitions in random structures.
Topics to be emphasized include

- Connections between equilibrium properties of Gibbs distributions in
statistical physics models and the efficiency of Markov chain
algorithms in computer science.
- Relationships between phylogeny algorithms in biology
and properties of the random cluster model from statistical physics
- Applications of advanced coupling techniques.
- Cutting-edge geometric techniques for bounding mixing rates, such as evolving sets

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on October 20, 2005.