Georgia Institute of Technology College of Sciences

We analyze the mixing time of a natural local Markov Chain (Gibbs sampler) for twocommonly studied models of random surfaces: (i) discrete monotone surfaces in Z3 with ``almostplanar" boundary conditions and (ii) the one-dimensional discrete Solid-on-Solid (SOS) model.In both cases we prove the first almost optimal bounds O(L^2 polylog(L)) where L is the natural size of the system. Our proof is inspired by the so-called ``mean curvature" heuristic: on a large scale, the dynamics should approximate a deterministic motion in which each point of the surface moves according to a drift proportional to the local inverse mean curvature radius. Key technical ingredients are monotonicity, coupling and an argument due to D.Wilson in the framework of lozenge tiling Markov Chains together with Kenyon's results on the free Gaussian field approximation of monotone surfaces. The novelty of our approach with respect to previous results consists in proving that, with high probability, the dynamics is dominated by a deterministic evolution which, apart from polylog(L) corrections, follows the mean curvature prescription. Our method works equally well for both models despite the fact that their equilibrium maximal deviations from the average height profile occur on very different scales (log(L) for monotone surfaces and L^{1/2} for the SOS model).This is work in collaboration with PIETRO CAPUTO and FABIO LUCIO TONINELLI

The 15th International Conference on Random Structures and Algorithms (RS&A) 2011 will be held at Emory University, May 24-28 (Tuesday-Saturday) 2011 and is co-organized by Emory University, Georgia Institute of Technology and Adam Mickiewicz University. The conference, organized biennially since 1983, brings together probabilists, discrete mathematicians and theoretical computer scientists working in probabilistic methods, random structures and randomized algorithms. The program will consist of one-hour plenary addresses by the invited speakers and parallel sessions of 25-minute contributed talks. It will begin on Tuesday morning and end on Saturday afternoon. The list of plenary speakers includes: Béla Bollobás [University of Cambridge and University of Memphis]; Jennifer Chayes [Microsoft Research New England, Cambridge]; Fan Chung [University of California, San Diego]; Jacob Fox [Massachusetts Institute of Technology]; David Gamarnik [Massachusetts Institute of Technology]; Jeff Kahn [Rutgers University]; Subhash Khot [Courant Institute]; Eric Vigoda [Georgia Institute of Technology]; Nick Wormald [University of Waterloo].

Come and see!