Spring 2010
Monday 34 pm
Room 2131
Schedule

February 8
David Gamarnik (MIT, Sloan School)
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
Abstract: We establish the existence of free energy limits for several diluted spin glass models, corresponding to combinatorial models on ErdosRenyigraphs. For a variety of models, including independent sets, MAXCUT, coloring and KSAT, we prove that the free energy both at a positive and zerotemperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zerotemperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem.For example, as a special case we prove that the size of a largest independent set in these graphs, normalizedby the number of nodes converges to a limit w.h.p., thus resolving an open problem.
Our approach is based on developing a combinatorial approach to the interpolation method recently developed in the statisticalphysics literature. Among other things, the interpolationmethod was used to prove the existence of free energy limits for VianaBray and random KSAT models.Our simpler combinatorial approach allows us to work with the zerotemperature case (optimization) directly and extend the approach to many other models.Additionally, using this approach we establish the large deviations principle for the satisfiability property for several constraint satisfaction problems.
Joint work with Mohsen Bayati (Stanford) and Prasad Tetali (Georgia Tech).

February 10
Partha Dey (Berkeley)
Central Limit Theorem for FirstPassage Percolation across thin cylinders
Abstract: We consider firstpassage percolation on the graph $\mathbb {Z} \times \{  h_n, h_n+1, \ldots, h_n \}^{d1}$ where each edge has an i.i.d.~nonnegative weight. The passage time for a path is defined as the sum of weights of all the edges in that path and the firstpassage time between two vertices is defined as the minimum passage time over all paths joining the two vertices. We will show that the firstpassage time $T_n$ between the origin and the vertex $ (n,0,\ldots,0)$ satisfies a Gaussian CLT as long as $h_n=o(n^{\alpha}) $ with $\alpha < 1/(d+1)$. The proof will be based on moment estimates, a decomposition of $T_n$ as an approximate sum of independent random variables and a renormalization type argument. Joint work with Sourav Chatterjee.

February 16
Gerard Ben Arous (Courant Institute)
Complexity of Random Morse functions, in the large N limit
Abstract: We relate the computation of the complexity of general Gaussian functions on the Sphere in large dimensions with Random Matrix theory. Using this link we compute their complexity, i.e their number of critical points, of given index on any level sets. We relate this question to the description of the the low energy states of spherical spin glasses. This joint work with A.Auffinger and J.Cerny.

February 22
Peter Tingley (MIT)
Random (skew) plane partitions
Abstract: Consider a random plane partition with N boxes, chosen with theuniform distribution. As was first shown by Vershik, for large N thepartition approximates a fixed limit shape with high probability(after appropriate rescaling). Okounkov and Reshetikhin observed thatthis system is equivalent to a certain Schur process, which can bedescribed in terms of nice transition functions. This allowed them togive an exact formula for the limit shape (recovering a result of Cerfand Kenyon), along with local correlation functions both in the bulkand near the frozen boundary. They have also studied skew planepartitions with these methods. Much of this talk will be an expositorypresentation of the work of Okounkov and Reshetikhin, but I will alsomention some recent work with Boutillier, Mkrtchyan and Reshetikhinwhere we expand on the results in the skew case.

February 24
SPECIAL SEMINAR: Wednesday, 34pm room 2142
Antti Kemppainen (Université ParisSud and University of Helsinki)
Random curves, scaling limits and Loewner evolutions
Abstract: In the 2D statistical physics and its lattice models, interfaces are random curves. A general method to prove the convergence of a random discrete curve, as the lattice mesh goes to zero, is to first show the existence of subsequent scaling limits and then to prove the uniqueness. In this talk, I will introduce a sufficient condition, and some equivalent formulations, that guarantee the precompactness (existence) and also that the limits are Loewner evolutions, i.e. they correspond to continuous Loewner driving processes. The second result is needed for the unique characterization of the limits. This framework of estimates can be used for almost all of the already existing proofs of an interface converging to a SchrammLoewner evolution (SLE), and for at least one new result. In principle, it can be applied beyond SLE.
Joint work with Stanislav Smirnov, Université de Genève

March 1
Cameron Freer (MIT)
Noncomputability of conditional probability
Abstract: Computer implementations of Bayesian statistics involve computingconditional probabilities for increasingly rich classes of randomvariables. Given a pair of computable random variables X and Y,the regular conditional distribution P[YX] is easily seen to becomputable when X is a discrete random variable. We present aconstruction that demonstrates that conditioning on continuousrandom variables is not, in general, a computable operation.
We also characterize a common setting involving exchangeablestochastic processes, where conditioning is computable, as aconsequence of a computable extension of de Finetti's theorem.
Joint work with Nate Ackerman (Berkeley) and Daniel Roy (MIT).

March 8
Eyal Lubetzky (Microsoft Research)
Cutoff for the Ising model on the lattice
Abstract: Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices.It is well known that at high temperatures, the time it takes this chain to mix in $L^1$ on a system of size $n$ is $O(\log n)$. Whether in this regime there is *cutoff*, i.e. a sharp transition in the $L^1$convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at $(c+o(1))\log n$for some fixed $c>0$, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the onedimensional Ising model, showing cutoff is a longstanding open problem.
We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. 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 continuoustime Glauber dynamics for the Ising model on $(\Z/n\Z)^d$ with periodic boundary conditions has cutoff at $(d/2\lambda_\infty)\log n$, where $\lambda_\infty$ is the spectral gap of the dynamics on the infinitevolume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited.
The proof hinges on a new technique for translating $L^1$mixing to $L^2$mixing of projections of the chain, which enables the application of logarithmicSobolev inequalities. The technique is general and carries to other monotone and antimonotone spinsystems, e.g.\ gas hardcore, Potts, antiferromagentic Ising, arbitrary boundary conditions, etc.
Joint work with Allan Sly.

March 15
Gregory F. Lawler (University of Chicago)
Tip multifractal spectrum for the SchrammLoewner Evolution (SLE)
Abstract: The tip multifractal spectrum of a curve f:(\infty, \infty) \rightarrow \Cis a way to measure the behavior of the derivativenear f(t) of a uniformizingmap of C \setminus f(\infty,t] to the upper halfplane. Wegive the almost sure multifractal spectrum of a chordalSLE curve. A special case of the result isBeffara's theorem on the Hausdorff dimension of thecurve. This derivative isrelated to the natural parameterization ofthe SLE curve. This is joint work with FredrikJohansson.

April 14
NOTE SPECIAL TIME: Wednesday, 34pm room 2142
Dmitry Ostrovsky
Limit loginfinitely divisible multifractals, intermittency differentiation, and Selberg integral as Mellin transform
Abstract: We will review the class of limit loginfinitely divisible processes of Muzy and Bacry (2002) and show how their invariances can be translated into functional FeynmanKac equations for the corresponding probability distributions. The talk will focus on the special case of the limit lognormal process of Mandelbrot (1972), Kahane (1985), and Bacry et al (2001). This process has the remarkable property that its positive integral moments are given by the celebrated Selberg integral. We will summarize our results on the equation of intermittency differentiation and its solutions on the form of formal intermittency expansions. The expansion for the Mellin transform is computed exactly and regularized by means of a momentconstant method giving an explicit analytic continuation of the Selberg integral as a function of its dimension to the complex plane.

April 21
Ron Peled (Courant Institute)
Highdimensional Lipschitz functions are typically flat
Abstract: A homomorphism height function is a function on the vertices of the discrete torus Z_n^d taking integer values and constrained to have adjacent verticestake adjacent integer values. We normalize the function to be 0 at a fixedvertex and consider the uniform distribution over all such functions. Thismodel is related to the uniform proper 3coloring model and in 2dimensions, tothe squareice model. Our main result is that in high enough dimensions, thefunction obtained is typically very flat, having constant height at any fixedvertex and taking at most C(log n)^{(1/d)} values. This matches a lowerbound of Benjamini, Yadin and Yehudayoff. The results have consequences also in2 dimensions and show a certain form of roughening transition on an n x log(n) torusas well as one side of a similar roughening transition on the n x n torus.Using a bijection of Ariel Yadin, the results carry over also to the related model ofLipschitz height functions. Our work generalizes results of Kahn and Galvin, refutesa conjecture of Benjamini, Yadin and Yehudayoff and answers a question of Benjamini,H\"aggstr\"om and Mossel.

April 28
NOTE SPECIAL TIME: Wednesday, 34pm room 2142
Tai Melcher (University of Virginia)
A Taylor isomorphism theorem on infinite dimensional Heisenberg groups
Abstract: It is well known that a holomorphic function on $\mathbb{C}$ is determined by the values of its derivatives at 0 via the Taylor expansion. Moreover, this map is an isometry from the space of holomorphic functions which are square integrable with respect to Gaussian measure to the sequence space of derivatives (equipped with an appropriate norm). There are several generalizations of this Taylor isometry, perhaps most notably the result of Driver and Gross in 1997 for holomorphic functions on complex Lie groups. I will discuss more recent results along these lines, in particular, for holomorphic functions on an infinite dimensional Heisenberg group which are square integrable with respect to a "subelliptic" heat kernel measure. This is joint work with Maria Gordina (Connecticut).

May 3
Laurent SaloffCoste (Cornell University)
The Dirichlet heat kernel in some Euclidean domains
Abstract: We try to identify a large class of unbounded domains (in Euclidean space or manifolds) in which the heat kernel with Dirichlet boundary condition can be precisely estimated. The results are obtained via a conceptual proof based on classical ideas: Doob's transform, volume doublingand Poincare inequalities.

May 10
Michael Anshelevich (Texas A&M)
Free Brownian motions on an algebra with two states.
Abstract: Free probability theory is a probabilitylike theory for noncommuting objects. Many familiar probabilistic results, starting with the centrallimit theorem, have very precise "free" analogs. In 1996, Bozejko,Leinert, and Speicher defined a new structure, which is similar to freeprobability but applies to algebras with _two_ expectations (states). Inthe algebraic context, this "twostate free probability theory" has alsobeen quite successful. I will show, however, that in this theory it reallymakes a difference whether one works in the algebraic or the analyticcontext: objects which exist in the algebraic setting may fail to existanalytically. The specific example I will describe are the (twostate)free Brownian motions. No noncommutative probability background will beassumed.

May 13
Joint Mathematical coloquium: Talk at 4:30 p.m. in Room 2190
Sourav Chatterjee (Berkeley)
A theory of chaos in disordered systems
Abstract: Disordered systems are an important class of models in statistical mechanics, having the defining characteristic that the energy function (Hamiltonian) is random. Examples include various models of spin glasses and polymers. They also arise in other disciplines, like fitness models in evolutionary biology. A disordered system is called chaotic if a small perturbation of the energy landscape causes a drastic change in some feature of the system, such as the ground state. In this talk I will present a series of basic new results about Gaussian random fields, that lead to a rigorous theory of chaos in disordered systems and confirms longstanding physics intuition about connections between chaos, anomalous fluctuations of the ground state energy, and the existence of multiple valleys in the energy landscape. As a specific application of the theory, (if time permits) I will sketch the resolution of the bond chaos conjecture for the SherringtonKirkpatrick model of spin glasses.
Fall 2011 Organizers
 Olivier Bernardi
 Henry Cohn
 Todd Kemp
 Scott Sheffield
 Dan Stroock