Room 210, Fields Institute
David Gamarnik, MIT
We discuss algorithmic hardness of solving combinatorial optimization
problems on sparse graphs by means of local algorithms. Recently a
framework for local algorithms was proposed based on the concept of
i.i.d. factors. In particular, it was conjectured that such an algorithm
should exist for the problem of finding a largest independent set
in a random regular graph. We disprove this conjecture by showing
that no local algorithm is capable of producing an independent set
larger that some multiplicative factor of the optimal. Our approach
is based on a powerful clustering phenomena discovered by statistical
physicists in the context of spin glass theory, and recently confirmed
by rigorous methods. To the best of our knowledge, our result is the
first direct application of the spin glass theory methods to the area
of algorithmic hardness.
Joint work with Madhu Sudan (Microsoft Research)
Stewart Library, Fields Institute
Pierre Patie, Cornell University
Some spectral problems associated to non-self-adjoint self-similar
We start this talk by showing a one-to-one correspondence between
the class of invariant Lamperti-Feller semi-groups and a subset of
negative definite functions. It turns out that these
non-self-adjoint semi-groups are closely related to positive self-similar
Feller processes which were introduced by Lamperti in 72 and have
been studied intensively recently. We proceed by showing the existence
of an intertwining relationship between this class of semi-groups
and the semi-group of a radial Ornstein-Uhlenbeck process, a self-adjoint
diffusion. Exploiting this connection, we provide NSF conditions for
the existence of discrete spectrum of this class of semi-groups. When
the spectrum is purely discrete we discuss eigenvalues expansions
by describing the sequence of eigenfunctions and co-eigenfunctions.
We also explain why this spectral expansion is indeed possible on
a space of functions which suffices for the description of the semi-groups
but fails on the full Hilbert space generated by the invariant measures
of the semi-groups.
This study is carried jointly with Mladen Savov (University of Reading,
Stewart Library, Fields Institute
Arno Kuijlaars, Leuven
The Hermitian two matrix model with quartic potential
I will discuss eigenvalues of random matrices from the Hermitian
two-matrix model with an even quartic potential. The mean limiting
eigenvalue distribution is governed by a vector equilibrium problem
for three measures with external fields and an upper constraint. Varying
the parameters one observes phase transitions at the closing or opening
of a gap in the limiting spectrum. The talk is based on joint work
with Maurice Duits (Stockholm) and Man Yue Mo (Bristol).
Room 210, Fields Institute
Tom Alberts, Caltech
Dimension Spectrum of SLE Boundary Collisions
In the range 4 < \kappa < 8, the intersection of the Schramm-Loewner
Curve (one of the central objects in the theory of 2-D Conformally
Invariant Systems) with the boundary of its domain is a random fractal
set. After reviewing some previous results on the dimension and measure
of this set, I will describe recent joint work with Ilia Binder and
Fredrik Viklund that partitions this set of points according to the
generalized "angle" at which the curve hits the boundary,
and computes the Hausdorff dimension of each partition set. The Hausdorff
dimension as a function of the angle is what we call the dimension
Probability Day Monday, March 18, 2013
University of Toronto, St George (downtown) campus.
Morning talks are in Wilson Hall, WI523
10:10 Peter Winkler, Darthmouth College: New Extremes for
Random Walk on a Graph
11:10 Michael Damron, Princeton University :Geodesics and
direction in first-passage percolation
12:30 Lunch, TBA
Afternoon talks are in Bahen, BA6183. This is inside the math department.
3:10 Richard Kenyon, Brown University: On the Ising model
4:10 Alice Guionnet, MIT: About heavy tails matrices
Room 230, Fields Institute
Ruth Williams (UCSD)
Correlation of Intracellular Components due to Limited Processing
A major challenge for systems biology is to deduce the molecular
interactions that underlie correlations observed between concentrations
of different intracellular components. Of particular interest is obtaining
an understanding of such effects when biological pathways share common
elements that are limited in capacity. Here we use stochastic models
to explore the effect of limited processing resources on correlations
when these resources are positioned downstream or upstream of the
molecular species of interest. Specifically, we consider two situations
where correlations in protein levels are the object of interest: (i)
degradation of different proteins by a common protease, and (ii) translation
of different mRNA transcripts by a limited pool of ribosomes. In developing
and analyzing stochastic models for these systems, we use insights
from the mathematical theory of multiclass queues which was originally
developed to understand congestion effects in telecommunication, computer,
manufacturing and business systems. In both models we observe a correlation
resonance: correlations tend to have a peak slightly beyond the point
where the systems transition from underloading to overloading of the
processing resources, although the sign of the correlation is different
in the two cases. As time permits, related experimental work will
This presentation is based on joint work with current or former members
of the UCSD Biodynamics lab and in particular with William H. Mather,
Natalie A. Cookson, Tal Danino, Octavio Mondragon-Palomino, Jeff Hasty
and Lev S. Tsimring.
Room 230, Fields Institute
Matthias Keller (Jena)
Absolutely continuous spectrum of Galton-Watson trees
We study the discrete Laplace operator on multi-type Galton-Watson
trees. We are interested in the case where the distribution of the
branching lies in a neighborhood of a deterministic one. These deterministic
trees are called trees of finite cone type and their spectrum consists
of finitely many bands of purely absolutely continuous spectrum.
So, whenever the distribution is not far from being deterministic
and such that each vertex has at least one forward neighbor, the operators
on the Galton-Watson trees inherit most of the absolutely continuous
spectrum from the deterministic case.
Room BA 3008,
Charles Bordenave (Toulouse)
An entropy for unimodular trees
Gabor Elek has proved that any unimodular tree with bounded degrees
is the Benjamini-Schramm local weak limit of a sequence of finite
graphs. We may then look for a quantitative version of this theorem
and try to compute the number of graphs of size n which are close
to a given unimodular tree. To perform this, we will introduce a natural
notion of entropy. We will deduce large deviations principles for
Erdos Renyi graphs and uniform graphs with given degree distribution.
This is a joint work with Pietro Caputo.
Arnab Sen (Cambridge)
A new approach to the Brownian web
The Brownian web corresponds informally to starting coalescing Brownian
motions from every space-time point in 1+1 dimensions. The standard
Brownian web, as defined by Fontes, Isopi, Newman and Ravishankar,
is the scaling limit of coalescing random walks as long as the third
moment of the jump distribution is finite. The third moment condition
is known to be also necessary for this convergence to hold. Inspired
by the work of Schramm and Smirnov on the scaling limit of critical
planar percolation, we provide a new state space and topology for
the Brownian web. In particular, this allows us to derive an invariance
principle for coalescing random walks under an optimal second moment
condition. Our approach is sufficiently simple and general that we
can prove similar invariance result for coalescing random walks on
Sierpinski gasket with little extra work. This is the first such result
where the limiting paths do not enjoy the non-crossing property.
Joint work with Nathanael Berestycki (Cambridge) and Christophe Garban
Christian Sadel (UBC)
Absolutely continuous spectrum for the Anderson model on trees
Trees are essentially the only structures where the existence of
absolutely continuous spectrum is known for the Anderson model (the
adjacency operator plus random potential). I will present one approach
based on supersymmetry.
Mike Molloy (Toronto)
Frozen Vertices in Colourings of a Random Graph
Over the past decade, much of the work on random k-SAT, colourings
of random graphs, and other random constraint satisfaction problems
has focussed on some foundational unproven hypotheses that have arisen
from statistical physics. Some of the most important such hypotheses
concern the clustering of the solutions. It is believed
that if the problem density is su?ciently high then the solutions
can be partitioned into clusters that are, in some sense, both well-connected
and well-separated. Furthermore, the clusters contain a linear number
of frozen variables, whose values are ?xed within a cluster.
The density where such clusters arise corresponds to an algorithmic
barrier, above which no algorithms have been proven to solve these
We prove that frozen vertices do indeed arise for k-colourings of
a random graph, when k is a su?ciently large constant, and we determine
the exact density threshold at which they appear.
Omer Angel (UBC).
Half planar maps
We characterise all measures on half planar maps that satisfy a domain
Markov property, and discuss some of their geometric properties. Joint
work with Gourab Ray.
Room BA 1180,
Balázs Szegedy (Toronto)
Couplings of probability spaces and related issues
Couplings of probability spaces are extensively used in probability
theory. One can use them to study the properties of various random
processes. We present a different view point where we represent various
algebraic and combinatorial structures in the coupling space of abstract
probability spaces. We demonstrate this direction in ergodic theory,
higher order Fourier analysis, and combinatorics (Sidorenko's conjecture).
Daniel Remenik (Universidad de Chile)
Determinantal line ensembles
During the last decade there has been a lot of interest in certain
stochastic processes which arise from families of non-intersecting
paths. Prominent examples are the Dyson Brownian motion from random
matrix theory and the Airy processes describing the spatial fluctuations
of certain random growth models. The distribution of these processes
are typically given by Fredholm determinants of what are known as
"extended kernels". Recently, a second type of Fredholm
determinant formula, in
terms of certain boundary value operators, has been very useful in
studying properties of Airy processes. I will explain how this second
type of formula holds in great generality and give examples of how
it can be applied to many processes of interest. Furthermore, I will
describe how this type of formulas can be obtained directly from the
non-intersecting nature of the families of paths considered (through
the Karlin-McGregor/Lindström-Gessel-Viennot formula).
This is joint work with A. Borodin and I. Corwin.
Michal Kotowski (Waterloo):
Random groups and property (T)
I will introduce the notions of random groups in Gromov model and
property (T). Random groups are an important object of study and a
source of interesting examples in geometric group theory. Then I will
sketch the proof that for density d > 1/3 random groups have property
(T) with high probability. The techniques used here come from spectral
graph theory and random graphs. The talk is based on the paper http://arxiv.org/abs/1106.2242.
Fields Institute, Room 210
Jeremy Quastel (University of Toronto)
How far does stuff get in an interacting system of asymmetric random
walks on Z^d?
In a system of non-interacting asymmetric random walks on Z^d a typical
particle's variance is order t. If the particles interact, the situation
is very different. A single particle may be sub-diffusive, but actually
what we really care about is the diffusivity of the bulk. This is
supposed to scale universally according to the local structure of
the flux, and the dimension. In lower dimensions it can be super-diffusive,
with very precise conjectures coming from rough physical arguments.
In joint work with Benedek Valko we give a proof of diffusivity/superdiffusivity
in the various regimes for a large class of such lattice gas models.
Nov. 9 at 2:10 p.m.
How long does it take to catch a drunk miscreant?
We discuss the answer to a question of Churchley who asked how long
it will take a cop to catch a drunk robber who moves randomly. We
begin by discussing other variants of the cop-robber paradigm. This
is joint work with Alex Scott, Colin McDiarmid, and Ross Kang.
BA6183, Bahen Center, 40 St George St
Of interest to the TPS: Math Department Colloquium
Ivan Corwin (Clay Mathematics Institute, MIT, Microsoft Research)
Over the last 15 years researchers in probability, integrable systems
and mathematical physics have uncovered a few important sources of
integrable probabilistic models which have allowed then to access
and describe universal phenomena of certain classes of disordered
systems. The purpose of today's talk is to identify one such universality
class containing growth models, driven diffusive lattice gases and
directed polymer models and explain how representation theory (in
the form of symmetric functions) serves as a significant source of
(University of Toronto)
How far is the random walker on a group?
On Z^d the expected distance of a walker from its starting point
after n steps is of order root n. On the free group (the regular tree),
it is of order n. What exponents apart from 1/2 and 1 are achievable?
I will explain why 1/2 is the minimal exponent. Nothing between 1/2
and 3/4 is known. I will also present a construction, joint with Gidi
Amir, that achieves every power between 3/4 and 1.
|No seminar October 15, 2012
due to Fields Medal
|TPS: Probability study
Talagrand's Majorizing Measures theorem
Viktor Harangi (University of Toronto)
Independent sets and the minimum eigenvalue in transitive graphs
Hoffman's theorem gives an upper bound on the independence ratio
of regular graphs in terms of the minimum eigenvalue of the adjacency
matrix. We use invariant Gaussian processes on graphs to get a lower
bound in the vertex-transitive case. Joint work with Bálint