Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
We establish the existence of free energy limits for several diluted spin glass models, corresponding to combinatorial models on Erdos-Renyi
graphs. 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 zero
temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero
temperature 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, normalized
by 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 statistical
physics literature. Among other things, the interpolation
method 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 zero
temperature 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)
--SPECIAL SEMINAR: Wednesday, 3-4pm, 2-255--
Central Limit Theorem for First-Passage Percolation across thin cylinders
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.
Complexity of Random Morse functions, in the large N limit
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
Consider a random plane partition with N boxes, chosen with the
uniform distribution. As was first shown by Vershik, for large N the
partition approximates a fixed limit shape with high probability
(after appropriate rescaling). Okounkov and Reshetikhin observed that
this system is equivalent to a certain Schur process, which can be
described in terms of nice transition functions. This allowed them to
give an exact formula for the limit shape (recovering a result of Cerf
and Kenyon), along with local correlation functions both in the bulk
and near the frozen boundary. They have also studied skew plane
partitions with these methods. Much of this talk will be an expository
presentation of the work of Okounkov and Reshetikhin, but I will also
mention some recent work with Boutillier, Mkrtchyan and Reshetikhin
where we expand on the results in the skew case.
February 24: Antti Kemppainen (Université Paris-Sud and University of Helsinki)
--SPECIAL SEMINAR: Wednesday, 3-4pm room 2-142--
Random curves, scaling limits and Loewner evolutions
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
Computer implementations of Bayesian statistics involve computing
conditional probabilities for increasingly rich classes of random
variables. Given a pair of computable random variables X and Y,
the regular conditional distribution P[Y|X] is easily seen to be
computable when X is a discrete random variable. We present a
construction that demonstrates that conditioning on continuous
random variables is not, in general, a computable operation.
We also characterize a common setting involving exchangeable
stochastic processes, where conditioning is computable, as a
consequence of a computable extension of de Finetti's theorem.
Joint work with Nate Ackerman (Berkeley) and Daniel Roy (MIT).
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.
Tip multifractal spectrum for the Schramm-Loewner Evolution (SLE)
The tip multifractal spectrum of a curve
f:(-\infty, \infty) \rightarrow \C
is a way to measure the behavior of the derivative
near f(t) of a uniformizing
map of C \setminus f(-\infty,t] to the upper half
plane. We
give the almost sure multifractal spectrum of a chordal
SLE curve. A special case of the result is
Beffara's theorem on the Hausdorff dimension of the
curve. This derivative is
related to the natural parameterization of
the SLE curve. This is joint work with Fredrik
Johansson.
April 14: Dmitry Ostrovsky --NOTE SPECIAL TIME: Wednesday, 3-4pm room 2-142--
Limit log-infinitely divisible multifractals, intermittency differentiation, and Selberg integral as Mellin transform
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)
--NOTE SPECIAL TIME: Wednesday, 3-4pm room 2-142--
High-dimensional Lipschitz functions are typically flat
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 vertices
take adjacent integer values. We normalize the function to be 0 at a fixed
vertex and consider the uniform distribution over all such functions. This
model is related to the uniform proper 3-coloring model and in 2-dimensions, to
the square-ice model. Our main result is that in high enough dimensions, the
function obtained is typically very flat, having constant height at any fixed
vertex and taking at most C(log n)^{(1/d)} values. This matches a lower
bound of Benjamini, Yadin and Yehudayoff. The results have consequences also in
2 dimensions and show a certain form of roughening transition on an n x log(n) torus
as 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 of
Lipschitz height functions. Our work generalizes results of Kahn and Galvin, refutes
a conjecture of Benjamini, Yadin and Yehudayoff and answers a question of Benjamini,
H\"aggstr\"om and Mossel.
April 28: Tai Melcher (University of Virginia)
--NOTE SPECIAL TIME: Wednesday, 3-4pm room 2-142--
A Taylor isomorphism theorem on infinite dimensional Heisenberg groups
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).
The Dirichlet heat kernel in some Euclidean domains
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 doubling
and Poincare inequalities.
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 central
limit theorem, have very precise "free" analogs. In 1996, Bozejko,
Leinert, and Speicher defined a new structure, which is similar to free
probability but applies to algebras with _two_ expectations (states). In
the algebraic context, this "two-state free probability theory" has also
been quite successful. I will show, however, that in this theory it really
makes a difference whether one works in the algebraic or the analytic
context: objects which exist in the algebraic setting may fail to exist
analytically. The specific example I will describe are the (two-state)
free Brownian motions. No non-commutative probability background will be
assumed.
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.