Allan Sly

Allan Sly

University of California, Berkeley
Department of Statistics
367 Evans Hall
Berkeley, CA 94720
sly@domain with domain = stat.berkeley.edu

I'm an assistant professor in the Department of Statistics at UC Berkeley. Previously I was a postdoc in the Theory Group at Microsoft Research and a PhD student at Berkeley under the supervision of Elchanan Mossel.

This semester I'm teaching Stat 155 Game Theory and Stat 206B Stochastic Process on graduate level discrete probability.



Research

My research is in discrete probability theory, often in problems from statistical physics or theoretical computer science. A major focus of my work has been on studying the mixing times of Markov chains, particularly the Glauber dynamics and the problem of cutoff for Markov chains. I have also worked on the reconstruction problem on trees. More recently I have also been interested in problems of random walks in random environments, random graphs and random matrices.


Selected Works

A complete list of publications and preprints is given here.

Critical Ising on the square lattice mixes in polynomial time
With E. Lubetzky (2010) To appear in Communications in Mathematical Physics Preprint.

Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the dynamics on $\Z^2$ everywhere except at criticality where only recently mathematicians have developed an understanding of its critical geometry with the advent of SLE. At the static phase-transition for Ising, the dynamics is conjectured to undergo a critical slowdown: At high temperature the inverse-gap is O(1), at the critical $\beta_c$ it is polynomial in the side-length and at low temperature it is exponential in it. A series of papers from the 80's and 90's verified in this on $\Z^2$ except at $\beta=\beta_c$ where the behavior remained an open problem. In this paper we establish the first rigorous polynomial upper bound for the critical mixing, thus confirming the critical slowdown for the Ising model in $\Z^2$. The proof harnesses recent understanding of the scaling limit of critical Fortuin-Kasteleyn representation of the Ising model together with classical tools from the analysis of Markov chains.

Computational Transition at the Uniqueness Threshold
Extended abstract in the proceedings of FOCS 2010.
Co-winner of the best paper award. Preprint.

We prove that at the uniqueness threshold of the hardcore model on the d-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree d. Specifically, we show that unless NP=RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree d for fugacity \lambda_c(d) < \lambda < \lambda_c(d) + \epsilon(d) where \lambda_c is the uniqueness threshold on the d-regular tree. Weitz produced an FPTAS for approximating the partition function when 0<\lambda < \lambda_c(d) so this result demonstrates that the computational threshold exactly coincides with the statistical physics phase transition thus confirming the main conjecture of Mossel, Wormald and Weitz [28]. The result establishes the first rigorous correspondence between the hardness of approximate counting with statistical physics phase transitions.

Cutoff for the Ising model on the lattice
With E. Lubetzky (2009) To appear in Inventiones Preprint.

In this paper we study the Glauber Dynamics Markov chain on the lattice. It is well known that at high temperatures the mixing time on a system of size $n$ is $O(\log n)$. This paper establishes cutoff, a sharp transition in the $L^1$-convergence to equilibrium in the high temperature regime. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For $\Z^2$ this carries all the way to the critical temperature. Specifically, for fixed $d\geq 1$, the continuous-time Glauber dynamics for the Ising model on $(\Z/n\Z)^d$ with periodic boundary conditions has cutoff at $(d/2\lambda)\log n$, where $\lambda$ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even the understanding of its stationary distribution is limited.

Cutoff phenomena for random walks on random regular graphs
With E. Lubetzky. Duke Mathematical Journal. 153 (2010), 475-510. Preprint.

It is well known that for $\G(n,d)$, a random $d$-regular graph on $n$ vertices, asymptotically almost every such graph for $d\geq 3$ is an expander, and even essentially Ramanujan. In this paper we establish cutoff, its location and an optimal $\sqrt{\log n}$ window with high probability for the simple random walk on random regular graphs. Even more precise results are derived for the the non-backtracking random walk where the cutoff window is of constant order.

Reconstruction of Potts Models
Annals of Probability 39, (2011), 1365-1406. Preprint.

The reconstruction problem on the tree has been studied in numerous contexts including statistical physics, information theory and computational biology. We prove the first exact reconstruction threshold in a non-binary model establishing the Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the $q$-state Potts model when $q \geq 5$. Moreover, we determine asymptotics for the reconstruction thresholds.


Header photo by A Brightman