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 Erdos-Renyigraphs. For a variety of models, including independent sets, MAX-CUT, coloring and K-SAT, 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 Viana-Bray and random K-SAT 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 First-Passage Percolation across thin cylinders

  Abstract: We consider first-passage percolation on the graph $\mathbb {Z} \times \{ - h_n, -h_n+1, \ldots, h_n \}^{d-1}$ 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 first-passage time between two vertices is defined as the minimum passage time over all paths joining the two vertices. We will show that the first-passage 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, 3-4pm room 2-142--

  Antti Kemppainen (Université Paris-Sud 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 Schramm-Loewner 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[Y|X] 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 one-dimensional 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 continuous-time 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 infinite-volume 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 logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g.\ gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.

  Joint work with Allan Sly.

• March 15

  Gregory F. Lawler (University of Chicago)

  Tip multifractal spectrum for the Schramm-Loewner 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, 3-4pm room 2-142--

  Dmitry Ostrovsky

  Limit log-infinitely divisible multifractals, intermittency differentiation, and Selberg integral as Mellin transform

  Abstract: We will review the class of limit log-infinitely divisible processes of Muzy and Bacry (2002) and show how their invariances can be translated into functional Feynman-Kac 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 moment-constant 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)

  High-dimensional 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 3-coloring model and in 2-dimensions, tothe square-ice 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, 3-4pm room 2-142--

  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 Saloff-Coste (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 probability-like theory for non-commuting 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 "two-state 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 (two-state)free Brownian motions. No non-commutative probability background will beassumed.

• May 13

  Joint Mathematical coloquium: Talk at 4:30 p.m. in Room 2-190

  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 long-standing 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 Sherrington-Kirkpatrick model of spin glasses.

Fall 2011 Organizers

• Olivier Bernardi
• Henry Cohn
• Todd Kemp
• Scott Sheffield
• Dan Stroock