New: This
seminar also has a google calendar entry: Weizmann - GFAP Seminar (Geometric Functional Analysis and
Probability)
October 7, 2010
Rani Hod, Tel
Aviv University, 3/2 firefighters are not enough
The firefighter problem is a
monotone dynamic process in graphs that can be viewed as modeling the use of a
limited supply of vaccinations to stop the spread of an epidemic. In more
detail, a fire spreads through a graph, from burning vertices to their
unprotected neighbors. In every round, a small amount of unburnt
vertices can be protected by firefighters. How many firefighters per turn, on
average, are needed to stop the fire from advancing?
We prove tight lower and upper bounds on the amount of firefighters
needed to control a fire in the Cartesian planar grid and in the strong planar
grid, resolving two conjectures of Ng and Raff.
This is a joint work with Ohad Feldheim.
------------------------------------------------------------
October 21, 2010
Barak Weiss, Ben Gurion
University, Infinite lattice surfaces and ergodicity
for Z-valued skew products over interval exchanges
Compact lattice surfaces (also known
as Veech surfaces) have been intensively studied over
the last 20 years. After a quick historical introduction to the theory of
compact lattice surfaces I will describe recent joint work with Pascal Hubert
and Pat Hooper in which we study non-compact lattice surfaces which arise as
Z-covers of compact ones. I
will discuss ergodicity
results for the straightline flow in these surfaces,
which give rise to new examples of ergodic Z-valued
skew products over interval exchanges.
------------------------------------------------------------
November 18, 2010
Senya Shlosman,
TBA
------------------------------------------------------------
December 23, 2010
Ori Gurel-Gurevich, TBA
------------------------------------------------------------
December 30, 2010
Anatoly Vershik,
Scaling entropy in ergodic theory and dynamics of
metrics
------------------------------------------------------------
January 13, 2010
Ivan Corwin, TBA
------------------------------------------------------------
June 10, 2010
Eric Shellef,
Weizmann, On the Range of a Random Walk in a Torus
Let a random walk run inside a torus of dimension three or higher for a number of steps
which is a constant proportion of the volume. We examine geometric properties
of the range, the random subgraph induced by the set
of vertices visited by the walk. We prove local distance and mixing bounds for
the typical range that are a k-iterated log factor from those on the full torus for arbitrary k. The proof uses hierarchical
renormalization and techniques that can be applied to more general random
processes in the Euclidean lattice.
------------------------------------------------------------
June 3, 2010
Mira Shamis,
Hebrew University, Preservation of absolutely continuous spectrum of
periodic Jacobi operators under perturbations of
square--summable variation
We discuss the preservation of the
absolutely continuous spectrum of Jacobi matrices
under perturbation. We shall survey the history of the problem, and then
discuss our result: the a.c. spectrum of a periodic Jacobi matrix (of period q) is preserved under perturbation
tending to 0 and having square-summable q-variation.
Based on joint work with Uri Kaluzhny
------------------------------------------------------------
May 27, 2010
Bert Zwart,
CWI Amsterdam, Scheduling and large deviations
We investigate the impact of a
scheduling discipline in preventing large response times in a queueing setting. In particular, for a single server queue
it is well known that, in a large deviations setting, FIFO is optimal for
light-tailed service times, and service disciplines such as PS (Processor
Sharing) and SRPT (Shortest Remaining Processing Time) are optimal for
heavy-tailed service times. It is also known that PS and SRPT do not perform
well for light-tailed service times, while FIFO does not perform well for
heavy-tailed service times. In this talk, we review these results, and answer
the natural question whether it is possible to construct a single scheduling
discipline that is competitive with FIFO for light-tailed service times and
competitive with SRPT for heavy tailed service times. We also investigate how
more robust scheduling disciplines can be designed by exploiting partial
information on the distributions, such as the system load.
------------------------------------------------------------
May 20, 2010
Vincent Beffara,
ENS Lyon, The self-dual point of the FK model in Z^2 is critical
------------------------------------------------------------
May 13, 2010
Swastik Kopparty,
MIT, Random graphs and the parity quantifier
The classical zero-one law for
first-order logic on random graphs says that for any first-order graph property
Q, as n approaches infinity, the probability that the random graph G(n, p) satisfies Q approaches either 0 or 1. It is well
known that this law fails to hold for any formalism that can express the parity
quantifier: for certain properties, the probability that G(n,
p) satisfies the property need not converge, and for others the limit may be
strictly between 0 and 1. In this talk, we describe the limiting behavior of
properties definable in first order logic augmented with the parity quantifier,
FO[parity], over G(n, p), which gently eludes the
above hurdles. Specifically, we establish the following "modular
convergence law":
For every FO[parity]
property Q, there are two rational numbers a_0, a_1, such that for i in {0,1}, as n approaches infinity, the probability that
the random graph G(2n+i, p) satisfies Q approaches a_i.
Our proof generalizes the original
quantifier elimination approach to the zero-one law, and is based on
polynomials over finite fields.
------------------------------------------------------------
April 29, 2010
Sebastian Müller,
Université de Provence, On probability and hyperbolic groups
In the first part we give a short
introduction to hyperbolic groups. In the second part we discuss stochastic
processes as random walks, branching random walks, and percolation on
hyperbolic groups and some of their qualitative behaviours.
------------------------------------------------------------
April 22, 2010
Nathan Keller, Weizmann,
A tight quantitative version of Arrow's Impossibility Theorem
A Generalized Social Welfare
Function (GSWF) is an election procedure in a society of n members,
where the members are given m alternatives, and each member chooses a
ranking of them. Then, the individual rankings are aggregated by some choice
function to the "total preference of the society" amongst each pair
of alternatives. The well-known Impossibility Theorem of Arrow shows a
surprising relation between several "natural" properties of GSWFs:
1. Independence of Irrelevant
Alternatives (IIA) -
the resulting preference amongst any pair of candidates depends only on the
individual preferences amongst that pair of candidates, and not on other
candidates.
2. Unanimity - if all the voters prefer
alternative A over B, then in the resulting preference A is also preferred over
B.
3. Dictatorship - the preference of the society
is determined by a single member.
4. Non-transitivity - the GSWF is non-transitive if there
exists a combination of individual preferences for which the society prefers A
over B, B over C, and C over A, for some alternatives A,B,C,
thus yielding a "paradox".
Arrow's theorem asserts that
any election procedure with at least three alternatives, which satisfies
the IIA condition and Unanimity and is not a dictatorship, is
necessarily non-transitive. In 2002, Kalai asked
whether one can obtain the following quantitative version of the theorem: For
any \epsilon>0, there exists \delta such that if a GSWF on
three alternatives satisfies the IIA condition and its probability of
non-transitive outcome is at most \delta, then the GSWF is at most \epsilon-far
from being a dictatorship or from breaching the Unanimity condition. In 2009, Mossel proved such quantitative version, with \delta=\exp(-C/\epsilon^{21}), and generalized it to GSWFs with m alternatives, for all m \geq 3.
In this talk we show that the
quantitative version holds with \delta=C \cdot
\epsilon^3, and that this result is tight up to logarithmic factors.
Furthermore, our result (like Mossel's) generalizes
to GSWFs with m alternatives. Our proof
is based on the works of Kalai and Mossel, but uses also an additional ingredient: a
combination of the Bonami-Beckner hypercontractive
inequality with a reverse hypercontractive inequality
due to Borell, applied to find simultaneously upper
bounds and lower bounds on the ``noise correlation'' between Boolean functions
on the discrete cube.
Despite the last paragraph, the talk
is intended to be self-contained...
-----------------------------------------------------------
March 25, 2010
Leif Doering,
TU Berlin, On Phase-Transitions for Interacting Diffusions
The talk is intended to introduce
some concepts and origins of systems of interacting diffusions indexed by a
lattice and their corresponding stochastic partial differential equation conterparts. In the first part, ideas and classical
questions for models from genetics, statistical physics, and probability theory
are going to be discussed. The second part focuses on recent results for a
particular example unifying some classical results from the first part.
To be more specific, in the second part we are going to talk about non-negative
solutions of the system of SDEs
du(t,i)=\Delta u(t,i) dt +\sqrt{u(t,i)v(t,i)} dB^1_t(i),
dv(t,i)=\Delta
u(t,i) dt +\sqrt{u(t,i)v(t,i)}
dB_t^2(i),
indexed by the lattice $Z^d$, where $\Delta$ denotes
the discrete Laplacian. Introducing correlations $\rho\in [-1,1]$ for the Gaussian noises, one obtains a
one-parameter family of interacting diffusions corresponding to well-known
models: Solutions for $\rho=1$ correspond to the
parabolic Anderson model with Brownian potential, for $\rho=0$
to the mutually catalytic branching model, and for $\rho=-1$
to the stepping stone model. Since these models exhibit quite a different
longtime behaviour solutions should behave
differently depending on $\rho$. We are going to
discuss results on the longtime behaviour in law,
almost surely, and of higher moments. In particular, we show that higher
moments $\E[u(t,k)^p],p>0$, are separated in
different regimes corresponding to exponential growth, subexponential
growth, and boundedness. An analogous result for a
continuous-space version can be used to strengthen a result on the wavespeed obtained by Etheridge/Fleischmann.
------------------------------------------------------------
March 18, 2010
Bruno Schapira,
Université Paris-Sud, The
excited Brownian motion as a limit of excited random walks on the set of
integers
(Multi-) Excited random walks (ERW)
on Z are among the most basic examples of non Markovian
self-interacting processes. Their transition probabilities depend on the time
they spent at their present location during the past. These processes were
introduced by Benjamini and Wilson in 2003 and then
extensively studied in the recent years. In the talk I will first review some
of the main known results (criteria for recurrence, positive speed, CLT). Then
I will speak about some continuous process, that we will call excited Brownian
motion (EBM), which is a semi-martingale whose drift is a function of its local
time at the present position. Benjamini suggested to
study EBM as a continuous version of ERW, and that they might behave similarly
as ERW. I will show that indeed criteria for recurrence, positive speed, and
CLT are similar to those for ERW. Moreover we will see that EBM might also be
seen as a weak limit of a sequence of renormalized ERWs.
(the talk is based on joint work with Olivier Raimond.)
------------------------------------------------------------
February 18, 2010
Allan Sly, Microsoft research, Computational
and physical phase transitions
Phase transitions in spin-systems
are widely believed to play a major role in the question of approximately
sampling from their
distributions. One such example is the hardcore model, the distribution
over independent sets S of a graph G weighted as \lambda^{|S|}. Weitz showed that it is possible to approximately sample
from from the hardcore model on graphs of maximum
degree d when it has uniqueness on the infinite d-regular tree (when \lambda
< \lambda_c(d) ). We show that above this
threshold when \lambda_c(d) < \lambda < \lambda_c(d) +\epsilon(d) there no polynomial time algorithm
for approximately sampling from the hardcore model on graphs of maximum degree
d unless RP=NP for some \epsilon(d) > 0 establishing a conjecture of Mossel, Weitz and Wormald. In the special case of \lambda=1 we further
show that it is computationally hard to approximately sample from the uniform
distribution on independent sets or approximately count them, on graphs of
maximum degree d=6 improving the previous result of d=24.
------------------------------------------------------------
January 21, 2010
Nir Lev, Weizmann,
Wiener's 'closure of translates' problem and Piatetski-Shapiro's
uniqueness phenomenon (joint work with A. Olevskii)
Wiener characterized the cyclic
vectors (with respect to translations) in l_p(Z) and L_p(R), p=1, 2, in terms of the zero set of the Fourier
transform. He conjectured that a similar characterization should be true for
1<p<2. I will discuss this conjecture.
------------------------------------------------------------
January 14, 2010
Marek Biskup,
UCLA, Overcoming convexity paradigm in gradient models
Gradient systems are models of
statistical mechanics and field theory where real-valued random variables
indexed by the integer lattice interact via a potential depending only on the
difference of the variables at two (close) points. When this potential is
convex, a number of techniques -- e.g. the Brascamp-Lieb
inequality, a random walk representation, a coupling to Langevin
dynamics, the cluster swapping algorithm -- are available and one can say a lot
about the infinite-volume Gibbs measures. In particular, there is exactly one ergodic Gibbs measure for each (average) tilt of the field,
the fluctuations scale to the Gaussian Free Field and the surface tension is
strictly convex in the tilt. Recently, the non-convex case has been tackled in
various works involving S. Adams, C. Cotar, R. Kotecky, S. Mueller, H. Spohn and
the speaker. I will review these results and outline the current state of
knowledge on this problem.
------------------------------------------------------------
January 13, 2010 (note unusual day)
Augusto Teixeira,
ETH, Interlacements percolation under small intensities
The model
of random interlacements was recently introduced by Alain-Sol Sznitman as a natural tool to understand the trace left by
a random walk in a discrete cylinder or in a discrete torus.
In these contexts, this model describes the microscopic "texture in the
bulk" left by the random walk when it is let run up to certain time
scales. In this talk we are going to discuss some percolative
properties of the vacant set of random interlacements under small intensities
(e.g. the size of a finite vacant cluster). The results which will be presented
could shed some light on problems such as how a random walk trajectory
disconnects a discrete cylinder into two infinite connected components.
------------------------------------------------------------
January 7, 2010
Uzy Hadad, Weizmann, On Kazhdan constants
of principle congruence subgroups
Recently Ershov
and Jaikin proved that the non-commutative universal
lattice ($EL_n(R)$) has Kazhdan's
property (T). This method appears fruitful for proving property (T) and
calculating Kazhdan constants for many discrete
groups. I will give a brief review of the main idea of this method.
Next, we generalized their method, and we give an explicit calculation of Kazhdan constants (asymptotic best possible) for the
principle congruence subgroups in $SL(n,Z)$ for some
'natural' bounded generating set. As a consequence we get Kazhdan
constants for infinite families of p-groups,
------------------------------------------------------------
December 31, 2009
Michael Hochman,
Princeton, local entropy averages and projections of fractal measures
If X is a compact set in the plane
then, by a classical theorem of Marstrand, almost
every projeciton onto a line maps X to a set of the
maximal possible dimension, i.e. the smaller of dim(X) and 1. An old conjecture
of Furstenberg's predicts that, if X=AxB, and A,B
are, respectively, subsets of the unit interval invariant under times-2 mod 1
and times-3 mod 1, then the image of X under every projection should behave
this way, the only exceptions being the coordinate projections. I will describe
recent work with Pablo Shmerkin in which we resolve
this conjecture and derive some related results.
-------------------------------------------------------------
December 30, 2009 (notice unusual
day)
Ron Peled,
New York University, 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äggström and Mossel.
-------------------------------------------------------------
December 24, 2009
Eyal Lubetzky,
Microsoft, Distances in random metrics: from weighted expanders to the
geometry of the random graph
How does the metric induced by an
expander graph change when random weights are placed on its edges? In
particular, how are typical and maximal distances affected by this perturbation?
A recent structure result for the largest component in the supercritical Erdos-Renyi random graph translates the study of its
geometry to these questions, where the role of the expander is played by a
random cubic graph. This enables us to read off key properties of the
supercritical random graph such as the diameter (whose asymptotics
for the full supercritical regime were unknown prior to this work), bounds on
longest simple paths and cycles etc. Prior estimates for these include works by
Luczak, Chung and Lu, Fernholz
and Ramachandran, Luczak
and Seierstad and Riordan and Wormald.
In the talk we will describe the reduction from the supercritical random graph
to the random perturbation of a random cubic graph. We will then demonstrate
how to characterize the geometry of the giant component via this reduction,
focusing on typical distances between vertices and the asymptotics
of the diameter.
-------------------------------------------------------------
December 3, 2009
Michael Björklund,
Royal Institute of Technology, Ergodic
theory and additive combinatorics
Given two sets in a countable abelian (or amenable) group, the sumset
(or product set) is defined as the set of all possible sums (or products)
between pair of elements in the two sets. Additive combinatorics
is to a large part concerned with estimates of the size of various sumsets. In this talk we will consider large sets (sets
with positive upper Banach density) in countable
amenable groups, and estimate the upper Banach
density of their sumsets from below. Even if this is
a discrete problem, our approach will be ergodic-theoretic
with a strong Fourier-analytic flavor. We establish sharp lower estimates in
the case when one of the sets is sufficiently aperiodic,
and characterize the end-cases. Joint work with A. Fish (Madison).
-------------------------------------------------------------
November 17, 2009
Nayantara Bhatnagar,
The Hebrew University, Sampling Contingency Tables with Cell-Bounded Entries
An mxn
contingency table is an array of non-negative integers whose row and column
sums are specified. In a cell-bounded contingency table, we also specify upper
and lower bounds on each of the entries. Sampling and counting such tables is
of interest in statistics and combinatorics.
Algorithms for approximate counting and sampling are known only in a number of
special cases. I will talk about an annealing algorithm for the case when the
cell bounds are all 0 or 1. Second, I will present some negative results for a
Markov chain proposed by Diaconis and Gangolli showing that in the cell-bounded case the chain
can fail to converge quickly.
The talk is based on joint works with Bezakova and Vigoda and with Bezakova
and Randall.
-------------------------------------------------------------
November 5, 2009
Eitan Bachmat,
Ben Gurion University, On some distributions which
make the management of express lines in the supermarket nice and easy
We set out to improve our
understanding of express lines in the supermarket.
About 150 years ago, and apparently with other goals in mind, Riemann
established the analytic continuation and the functional equation for his Zeta
function by considering it as the function of moments of a modular form.
We will try to explain how these projects seem to parallel each other.
The talk will be self contained.
-------------------------------------------------------------
October 29, 2009
Van Cyr, Penn State University, Obstructions
to the Existence of Equilibrium Measures for Countable Markov Shifts
The goal of this talk is to present
several new results aimed at showing:
1. In the space of all potentials on
a countable Markov shift, the set of potentials that have a (generalized)
equilibrium measure is L-infinity-open and Lipschitz-dense.
2. There is a (simple) combinatorial
condition on the shift which is necessary and sufficient for the complement of
this set to be nonempty; “most" shifts satisfy it. In this case we
show that, in a suitable topology, the phenomenon of transience is open and
dense in this complement.
-------------------------------------------------------------
October 22, 2009
Nicholas Crawford, Technion, Heat Kernel Upper Bounds for Long Range
Percolation Clusters
In this talk I will detail recent
joint work with Allan Sly on the behavior of simple random walk on long range
percolation clusters on Z^d. There is a well
developed connection between the geometry of a (finite) graph and the size of
its spectral gap. This connection extends to infinite graphs with respect to
bounds on the decay of the heat kernel but requires knowledge of the geometry
on many different scales simultaneously. Our goal in this talk is to describe
the method by which we obtain the necessary control for the LRP model.
-------------------------------------------------------------
September 24, 2009
Johan Tykesson,
Weizmann, Visibility to infinity in the hyperbolic
plane, despite obstacles
Consider a Poisson point process X
in the hyperbolic plane with some intensity lambda. Around each point in X, center
a ball of radius R. We show that if lambda is big enough, the union of the
balls contains infinite geodesic lines. If lambda is low enough, it turns out
that the complement of the balls contains infinite geodesics. It is possible to
calculate the critical lambda for this phase transition exactly. We also show
similar results for a wider class of random sets in the hyperbolic plane.
Related problems will be discussed.
-------------------------------------------------------------
September 17, 2009
Michael Elkin, Ben Gurion University, Improved Construction of
Progression-Free Sets
The problem of constructing dense
subsets S of {1,2,..,n} that contain no arithmetic triple was introduced by Erdos and Turan in 1936. They
have presented a construction with |S| = Omega(n^{log_3 2}) elements. Their
construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend
is |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} \cdot \log^{1/4}
n}} ). Since then the problem became one of the most central, most fundamental,
and most intensively studied problems in additive number theory. Nevertheless,
no improvement of the lower bound of Behrend was
reported since 1946.
In this paper we present a construction that improves the result of Behrend by a factor of Theta(sqrt{log
n}), and shows that |S| = Omega({ n \over {{2^{2 \sqrt{2}
\sqrt{\log_2 n}}} }} \cdot
\log^{1/4} n ). In particular, our result implies that the construction of Behrend is not optimal. As part of the proof we consider
the set S of integer lattice points that lie in the intersection of a
high-dimensional thin annulus A with a hypercube, and show that as long as the
annulus A is sufficiently thin, the boundary set of the convex hull of of S contains at least Omega(|S|) points.
Our construction and proof are elementary and self-contained. It is based on
ideas from Discrete Geometry. Also, the construction can be implemented by an
efficient algorithm.
Behrend construction has numerous applications in Theoretical
Computer Science. In particular, it is used for fast matrix multiplication, for
property testing, and in the area of communication complexity. Plugging in our
construction instead of Behrend construction in the
matrix multiplication algorithm of Coppersmith and Winograd
improves the state-of-the-art upper bound on the complexity of the matrix
multiplication
by a factor of log^\delta n, for some fixed constant delta > 0. We also
present an application of our technique in Discrete and Computational Geometry.
-------------------------------------------------------------
September 10, 2009
Simone Warzel,
T. U. Munich, Extended States on Trees
Abstract: We will survey some
results and their proofs on the occurrence of absolutely continuous spectrum
and its implications for random operators on tree graphs.
-------------------------------------------------------------
September 3, 2009
David Windisch,
Weizmann, Random walks, disconnection and random
interlacements
Abstract: The disconnection of discrete
cylinders and integer tori by trajectories
of random walks has been the object of recent interest. We will see links
between these problems and the model of random interlacements.
-------------------------------------------------------------
July 23,
Abstract: A quadrature
formula for a given measure is a discrete measure having the same
first moments. I will survey
classical results in the theory of the (truncated)
moment problem, concentrating on the
Gaussian and related quadratures. One
application of these results is to
find the optimal tail bound for a random
variable given only the knowledge of
its first moments. I will then shift to
discuss Chebyshev-type
quadratures - quadratures
with all equal weights. I will
explain the problem of finding
quantitative bounds for the size of such
quadratures and discuss known and new results.
Throughout, I will mention open
problems.
The talk is mostly of a survey
nature and no prior knowledge on quadratures is
required.
-------------------------------------------------------------
July 16,
Tobias Mueller,
abstract: Let $X_1,\dots, X_n$ be independent, uniformly random points from
$[0,1]^2$. We prove that if we add edges between these points one by one by
order of increasing edge length then, with probability tending to 1 as the
number of points $n$ tends to $\infty$, the resulting
graph gets its first Hamilton cycle at exactly the same time it loses its last
vertex of degree less than two. This answers an open question of Penrose and
provides an analogue for the random geometric graph of a celebrated result of Ajtai, Koml{\'o}s and Szemer{\'e}di and independently
of Bollob\'as on the usual random graph. We are also
able to deduce very precise information on the limiting probability that the
random geometric graph is Hamiltonian analogous to a result of Koml{\'o}s and Szemer{\'e}di on the usual random graph. The proof generalizes to
uniform random points on the $d$-dimensional hypercube where the edge-lengths
are measured using the $l_p$-norm for some $1<p\leq\infty$. Time permitting, I will also give some other
results on
-------------------------------------------------------------
Abstract: A subset of the real line
has measure 0 if and only if some
Lipschitz function is not differentiable
anywhere in this set. But in higher
dimensions, whilst the
"if" part is still true, there exist exceptional
sets of measure 0 such that every Lipschitz function is differentiable on
a dense subset of the set. I will
show that such sets can even be compact
and of Hausdorff
dimension 1. I will explain why this is a step towards a
solution of a long-standing open
problem in geometric measure theory.
-----------------------------------------------------------
July 2, 2009
Abstract: In this talk we will show that the unit cube is a strict local minimizer for the Mahler volume product $vol_n(K)vol_n(K^*)$ in the class of origin symmetric convex bodies endowed with the Banach-Mazur distance (joint work with F. Nazarov, F. Petrov and D. Ryabogin).
------------------------------------------
Nathan Keller, Hebrew University, Noise Sensitivity of Functions on the Discrete Cube - Quantitative Results
Abstract: A Boolean function f:{0,1}^n -> {0,1} is called "noise sensitive" if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [BKS] showed that if the influences of all the coordinates on f are small then it must be noise sensitive (the formal condition is that the sum of squares of the influences is o(1).)
[BKS] showed a quantitative relation between the sum of squares of the influences and the noise sensitivity only when the sum of squares is bounded by n^{-c} for a constant c. We show a relation that is independent of n, and prove that it is tight. Our results hold also for a general product measure \mu_p on the discrete cube, as long as \log 1/p << \log n.
Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions.
In order to achieve it, we present a considerably shorter proof of Talagrand's lemma, which easily generalizes in various directions, including non-monotone functions.
Joint
work with Guy Kindler.
------------------------------
Nicolas Curien, ENS Paris and University Paris-Sud, Scaling limit of large random planar maps and the brownian map
Abstract: Scaling limit of large random planar maps and the brownian map. A planar map is an embedding of a graph in the two-dimensional sphere. In the spirit of Donsker's theorem which says that nice random walks suitably rescaled converge toward brownian motion, we will discuss convergence of rescaled planar maps toward an random surface called brownian map. The sense of the convergence, and the limiting objects will be defined in the talk. Some properties of brownian maps will be exposed. For example, brownian maps are random metric spaces a.s. homoemorphic the sphere but with Hausdorff dimension equal to 4.
-----------------------
Wednesday, June 3, 2009, 11:00-13:00, Room 229 (Pekeris),
Martin Zerner, University of Tubingen, Lyapunov exponents of Green's functions for random potentials tending to zero.
Abstract:
We consider the Green's function G_V(x,y) of -Laplacian+V on the lattice Z^d,
where the potential V consists of i.i.d. nonnegative
random variables V(z), z in Z^d. It is well-known
that for any non-zero y in Z^d both G_V(0,ny) and its
expected value E[G_V(0,ny)] tend exponentially fast to 0 as n tends to
infinity. The exponential rates of decay of these two quantities are denoted by
A_V(y) and
B_V(y)
and are called the quenched and the annealed Lyapunov
exponent, respectively.
In joint work with Elena Kosygina and Thomas S. Mountford we consider
A_{gamma*V}(y) and B_{gamma*V}(y), where gamma>0 is a scalar. Under the assumption that the potential has a finite first moment E[V(0)] we present a probabilistic and relatively elementary proof that both Lyapunov exponents scale like c*sqrt(gamma) as gamma tends to 0. Here the constant c is the same for the quenched as for the annealed exponent and is known explicitly. This improves results obtained previously by Wei-Min Wang.
----------------------------------------------------------------------------------------
Atilla
Yilmaz, Weizmann, A
recent result on the equality of the quenched and averaged large deviation rate
functions for random walk in a random environment
Abstract: Consider large deviations for nearest-neighbor random walk in a uniformly elliptic i.i.d. environment. It is easy to see that the quenched and averaged rate functions are not identically equal. When the dimension is at least four and Sznitman's transience condition (T) is satisfied, I recently proved that these rate functions are finite and equal on a closed set whose interior contains every nonzero velocity at which the rate functions vanish. In this talk, I will present the proof of this result (except that I might skip some technical parts.)
--------------------------------------------------
Abstract:
The Gowers uniformity norms U_k
measure a certain kind of psuedo randomness. For
example, a function f on a finite (large) dimensional vector space V over a
finite field F has small U_2 norm if and only if all its Fourier coefficients
are small - i.e it has no significant correlation
with linear phase functions. The content of the inverse conjecture for the Gowers norms is that a similar relation exists between the U_k norms and polynomials of degree smaller than k; namely
a function f has small U_k norm if and only if it has
no significant correlation with a polynomial phase function of degree smaller
than k. This conjecture plays an important role in counting solutions to
systems of linear equations in subsets of vector spaces, and in polynomiality testing.
I
will describe a proof of this conjecture in the case where char(F) is greater
equal k, using tools from ergodic theory. In the low
characteristic case, we show that if f has small U_k
norm then it has no significant correlation with a polynomial phase function of
bounded degree c(k).
I will define all relevant notions. Joint works with V. Bergelson and T. Tao.
----------------------------------------------------
Alexander Its, Indiana University, Painleve Transcendents and Random matrices.
Abstarct: Painlev\'e functions have been playing increasingly important role in random matrix theory since the early nineties works on the 2d quantum gravity of Br\'ezin and Kazakov, Duglas and Shenker, and Gross and Migdal and the works (also early nineties) of Mehta and Mahoux, and Tracy and Widom on the level spacing distributions. Indeed, the appearance of Painlev\'e fucntions in the field can be traced to 1970s-1980s works of Barouch, McCoy, Tracy, and Wu, and of Jimbo, Miwa, Mori and Sato on the quantum correlation functions. In this talk we will try to review these, and also some of the more recent results concerning Painlev\'e transcendents and random matrices. We will present a unified point view on the subject based on the Riemann-Hilbert method. The emphasis will be made on the various double scaling limits related to the universal properties of random matrices for which Painlev\'e functions provide an adequate ``special function environment''.
----------------------------------------------------
Sebastian Müller, Weizmann, From Branching Markov chains to infinite-type Galton-Watson processes,
some qualitative characteristics
Abstract: A branching Markov chain (BMC) is a system of particles in discrete
time. The BMC starts with one particle in an arbitrary starting position $x$.
At each time particles split up in offspring particles independently according
to some probability distributions that may depend on the locations of the
particles. The new particles then move independently according to a Markov
chain. An irreducible Markov chain is either recurrent or transient: either all
or none states are visited infinitely often. It turns out that this dichotomy
breaks down for BMC and that one can classify BMCs in
three different types. Let $\alpha(x)$ be the probability that, starting the
BMC in $x$, the state $x$ is hit infinitely often by some particles. There are
three possible regimes: transient $(\alpha(x) = 0 \forall
x)$, weakly recurrent $(0 < \alpha(x) < 1 \forall
x)$ and strongly recurrent $(\alpha(x) = 1 \forall
x)$. We give equivalent criteria for transience of BMC and discuss some
consequences concerning generating functions and embedded branching
processes.
It is well known that a Galton-Watson process dies
out almost surely if the mean number of offspring $m$ is less or equal $1$ and
survives with positive probability if $m>1.$ The same is true for
finite-type Galton-Watson processes where the
threshold between extinction and survival is the Perron-Frobenius
eigenvalue of the first moment matrix. The behaviour of infinite-type Galton-Watson
processes is more subtle; here four different notions of survival may occur.
Note that a BMC is a special type of infinite-type Galton-Watson
processes. We will discuss these different types and give a criterion for local
extinction and local survival in general and for global extinction and global
survival in some examples.
-----------------------------------------------------------------
Jean-Dominique
Deuschel, Berlin, Invariance principle for the
random conductance model with unbounded conductances
abstract:
We study a continuous time random walk $X$ in an environment of i.i.d.
random
conductances $\mu_e \in
[1,\infty)$. We obtain heat
kernel
bounds and prove a quenched invariance principle for $X$.
This
holds even when $\bE \mu_e
= \infty$.
Joint work with M. T. Barlow
Keywords:
Random conductance model, heat kernel, invariance principle, corrector.
-------------------------------------------------------------------
March 5, 2009,
Abstract: Consider the classical balls-and-bins setup: n balls are thrown independently and uniformly into n bins. The most loaded bin then has log n/log log n balls with high probability. What happens when instead of throwing balls completely by random, there is an allocation algorithm which is given k uniformly and independently selected bins to choose from for the location of each ball? A well known result of Azar, Broder, Karlin & Upfal states that one can then achieve a maximal load of log_k log n, simply by putting the ball in the less loaded of the k bins. In order to implement this simple algorithm, one needs to keep track of the status of the entire array of n bins, which naively requires n log n bits of memory (and can be done non-naively with just 2n bits).
The
problem of what can be achieved under memory restrictions was raised by
A key ingredient in the proofs of the lower bounds is a large deviation inequality, which relates the sum of a sequence of bounded dependent random variables with the sum of their conditional expectations. This inequality may prove useful in other combinatorial or algorithmic problems.
Joint work with Noga Alon and Eyal Lubetzky.
--------------------------------------------------------------
WEDNESDAY, March 4, 2009,
Abstarct: The spectral gap of a doubly stochastic matrix is the reciprocal of the best constant in its associated Poincare inequality. This inequality can be formulated in purely metric terms, where the metric is a Hilbertian metric. This immediately allows us to define the spectral gap of a matrix with respect to other, non-Euclidean, geometries: a standard procedure which is used a lot in embedding theory, most strikingly as a method to prove non-embeddability in the coarse category. Motivated by a
combinatorial approach to the construction of bounded degree graph families which do not admit a coarse embedding into any uniformly convex nomed space (such spaces were first constructed by Lafforgue), we will naturally arrive at questions related to the behavior of non-linear spectral gaps under graph operations such as powering and zig-zag products. We will also discuss the issue of constructing base graphs for these iterative constructions, which lead to new analytic and geometric challenges.
Joint
work with
------------------------------------------------------------------
Rom Pinchasi, Technion, Using Duality and Euler's formula in the plane
Abstract: We will present the principle of duality between points and lines in the plane in connection with Euler's formula. We will then present two examples of using these simple principles in giving surprisingly elegant solutions to long standing open problems.
--------------------------------------------------------------------
February 12, 2009
Alice Guionnet, Ecole Normal Superieure de Lyon, Topological expansion for random matrices Abstarct: Integrals of random matrices are known to be related to
the enumeration of graphs
sorted by their genera since
the work of 't Hooft and Brezin, Itzykson, Parisi and
Zuber in the seventies. We shall review this idea and
recent progresses in mathematics in this direction.
------------------------
Abstract: We shall discuss the distribution of extreme eigenvalues for several classes of random matrices with independent entries. In particular,we shall discuss the results of Soshnikov and some of their recent extensions, and the combinatorial questions that appear in the proofs. Based on joint work with Ohad Feldheim.
-----------------------
Nayantara
Bhatnagar,
Consider the uniform distribution over k-colorings of the complete tree of height h and branching factor D. As h tends to infinity, for what values of k is the color at the root conditioned on a fixed coloring of the leaves uniformly distributed over all k colors? It is straightforward to show the existence of colorings of the leaves which ``freeze'' the entire tree when k \le D+1. What happens for a typical coloring of the leaves? When the leaves have a non-vanishing influence on the color of the root in expectation over random colorings of the leaves, reconstruction is said to hold.
When k < D/ ln(D), it is known that reconstruction is possible while for k > D it is easy to show that reconstruction is not possible. We prove that for k > D/ ln(D), with high probability over the colorings of the leaves the influence at the root decays exponentially fast with the depth of the tree and reconstruction does not hold.
-----------------------------------------------------------------------------------------------------
Eyal Lubetzky, Microsoft Research, Cutoff phenomena for
random walks on random regular graphs
Abstract:
The cutoff phenomenon describes
a sharp transition in the convergence of a family of ergodic
finite Markov chains to equilibrium. Many natural families of chains are
believed to exhibit cutoff, and yet establishing this fact is often extremely
challenging. An important such family of chains is the random walk on G(n,d), a random d-regular graph on n vertices. It is well
known that the spectral gap of this class of chains for d fixed is constant, implying
a mixing-time of O(\log n). According to a conjecture of Peres, the simple
random walk on G(n,d) for any fixed d should then
exhibit cutoff whp. As a special case of this, Durrett conjectured that the mixing time of the lazy random
walk on a random 3-regular graph is whp
(6+o(1))\log_2(n).
In this work we confirm the
above conjectures, and establish cutoff in total-variation, its location and
its optimal window, both for simple and for non-backtracking random walks on G(n,d). Namely, for any fixed d, the simple random walk on G(n,d) whp has cutoff at
[d/(d-2)]\log_{d-1}(n) with window order \sqrt{\log
n}. Surprisingly, the non-backtracking random walk on G(n,d)
whp has cutoff already at \log_{d-1}(n) with constant
window order. We further extend these results to G(n,d)
for any d=n^{o(1)} (beyond which the mixing time is O(1)), provide efficient
algorithms for testing cutoff, as well as give explicit constructions where
cutoff occurs.
Joint work with Allan Sly.
------------------------------------------------------------------------------
Abstract:
We consider a Poisson point process in the plane. Its Voronoi
diagram is
the partition of the plane defined by matching to every point of the
Poisson process those points of the plane which are closer to it than to
any other point of the Poisson process. Like all planar maps, the
Poisson-Voronoi diagram can be (properly) colored
with 4 colors. But how
many colors are required to do it in a translation-equivariant
way? (roughly speaking,
we ask for a coloring algorithm which does not depend on a starting point. In
dimension 1, 2 colors are enough for non-equivariant
colorings, but 3 are
needed for equivariant ones).
Our main result is that this can be done with 6 colors. The construction is
a variant of the 6 coloring algorithm for finite planar maps, and its analysis
requires probabilistic estimates showing that the coloring produced is
"almost independent" at large distances.
Other results and the cases of dimensions one and three will also be discussed.
This is joint work with Omer Angel,
---------------------------------------------------
Ilya Goldsheid, Queen Mary University of London, Lyapunov exponents of products of non-identically
distributed random matrices.
----------------------------------------------------
Ariel
Yadin, Weizmann, Loop-erased
random walk on planar graphs
Abstract:
This
talk focuses on loop-erased random walk, or LERW. LERW is a random self-avoiding curve obtained
by erasing the loop in the trajectory of a random walk in chronological
order. Lawler, Schramm, and Werner
proved that LERW on the Euclidean plane converges to SLE(2) as the mesh goes to
0. SLE, or Schramm-Loewner
Evolution, is a fascinating random process discovered by Oded
Schramm in 1999. SLE arises as the
scaling limit of many models in mathematical physics. It has many wonderful properties, perhaps the
most important is ``conformal invariance".
Lawler,
Schramm, and Werner's proof for the scaling limit of LERW essentially uses the
symmetry of the lattice structure. The
question arises whether a similar result holds even under perturbed lattices;
for example, if only a small portion of edges are removed from the original
lattice.
We
extend Lawler, Schramm and Werner's result:
For any planar Markov chain (that is a Markov chain embedded into the
complex plane so that edges do not cross one another), if the scaling limit of
the Markov chain is planar Brownian motion, then the scaling limit of the loop
erasure of the Markov chain is SLE(2).
One main example, is loop-erased random walk on the super-critical
percolation cluster; that is, the infinite component after super-critical
percolation on $Z^2$. Berger and Biskup showed that the random walk on the super-critical
percolation cluster converges to Brownian motion. Thus, our result implies that the loop-erased
random walk on the super-critical percolation cluster converges to SLE(2).
Joint
work with Amir Yehudayoff.
---------------------------------------------------
Uri Shapira,
Hebrew University, A solution to an open problem of Cassels
Abstract: We prove existence of
real numbers x,y, possessing the following property:
For any real a,b,
liminf n ||nx - a|| ||ny - b|| = 0, where ||c|| denotes the distance of c to the
nearest integer.
This answers a 50 years old
question of Cassels.
The most interesting part of the
result is that there are algebraic numbers with the above property!!!
In the lecture we shall make
friends with two nice spaces: The space of lattices and the space of grids. We
shall investigate dynamical questions in these spaces and derive the above
results from the dynamical information.
-----------------------------------------------------------------------------
Allan Sly, University of California, Berkeley, Mixing on Random Graphs
Abstract: Understanding Gibbs measures on trees and their spatial mixing thresholds (uniqueness, strong spatial mixing, reconstruction) can give insight into the behavior of Gibbs measures on general graphs, in particular random graphs which are locally tree-like. We discuss mixing of the Glauber dynamics of the Ising model and random colourings and their relationship to spatial mixing thresholds.
Based on joint work with E. Mossel.
----------------------------------
Abstract: We show that for convex domains in Euclidean space, Cheeger's isoperimetric inequality, spectral gap of the Neumann Laplacian, exponential concentration of Lipschitz functions, and any arbitrarily slow (but fixed) tail-decay of these functions, are all equivalent (to within universal constants, independent of the dimension). This substantially extends previous results of Maz'ya, Cheeger, Gromov--Milman, Buser and Ledoux. As an application, we conclude a sharp quantitative stability result for the spectral gap of convex domains under convex perturbations which preserve volume (up to
constants) and under maps which are ``on-average'' Lipschitz. We also provide a new characterization of the Cheeger constant for convex domains, as one over the expectation of the distance from the ``worst'' Borel set having half the volume of the domain. In addition, we easily recover (and extend) many previously known lower bounds, due to Payne--Weinberger, Li--Yau, Kannan--Lov\'asz--Simonovits, Bobkov and Sodin, on the Cheeger constant of convex domains. The proof involves estimates on the diffusion semi-group following Bakry--Ledoux and a result from Riemannian Geometry on the concavity of the isoperimetric profile. Our results extend to the more general setting of Riemannian manifolds with density which satisfy the $CD(0,\infty)$ curvature-dimension condition of Bakry-\'Emery.
----------------------------------------------------
This talk will give an overview of some recent results on inapproximability of NP-complete problems and their connections to discrete Fourier analysis and isoperimetric problems.
----------------------------------------------------
July 10, 2008
Gerard
Ben-Arous, Courant Institute, TBA
-----------------------------------------------------
Abstract: In 1985 Bourgain gave a discrete metric characterization of
when a normed space admits an equivalent uniformly convex norm: this
happens if and only if the space does not contain arbitrarily large
complete binary trees with low distortion. Bourgain's theorem was the
first successful step in a research program that was inspired by a
theorem of Ribe from 1976, which suggested that certain linear
properties of normed spaces are actually metric properties in
disguise. In this talk we will revisit Bourgain's solution in a
quantitative way: we will obtain a metric characterization of the
degree to which a norm is uniformly convex. It turns out that this
question exhibits unexpected subtleties and surprising differences
from the linear theory of normed spaces and from the theory of metric
type and cotype. Nevertheless, we will be able to show that a normed
space has an equivalent norm with modulus of uniform convexity of
power type p if and only if a concrete metric inequality called Markov
p-Convexity is satisfied. This inequality controls the rate at which certain
Markov chains diverge in a metric space, and it is useful for problems in metric
geometry which do not necessarily involve linear spaces. We will
discuss some of these applications, as well as some unexpected counterexamples.
Joint work with Manor Mendel.
---------------------------------------------------------------
We
consider one-dimensional Brownian motion conditioned (in a suitable
sense)
to have a local time at every point and at every moment bounded by some fixed
constant. Our main result shows that a phenomenon of entropic repulsion occurs:
that is, this process is ballistic and has an asymptotic velocity approximately
4.5860... as high as required by the conditioning (the exact value of this
constant involves the first zero of a Bessel function). I will also describe
other conditionings of Brownian motion in which this principle of entropic
repulsion manifests itself.
Joint
work with Itai Benjamini.
-------------------------------------------------------------------
Considering the Sherrington-Kirkpatrick Model of spin glasses, Comets and Neveau showed (among other things) that if there is no external field, the energy density satisfies a quenched CLT in the limit as the volume tends to infinity using Martingale Convergence Theorems. Rececently, Chatterjee gave an independent proof of this result using Stein's Method, and also applied this technique to prove limit laws for a number of other observables, such as local fields.
However, considering the flucatuations of the energy density in a non-zero external field, neither of these methods apply. Thus, the general case was left open and it was not clear how to proceed.
In this talk we resolve this problem, applying a combination of the cavity method and Stein's method, a powerful quantitative tool for proving CLT's (in the high temperature region).
Based on joint work w/ Sourav Chatterjee.
-------------------------------------------------------------------
Bond percolation on a graph G with parameter p in [0,1] is the random subgraph G_p of G obtained by independently deleting each edge with probability 1-p and retaining it with probability p. For many graphs, the size of the largest component of G_p exhibits a phase transition: it changes sharply from logarithmic to linear as p increases. When G is the complete graph, this model is known as the Erdos-Renyi random graph: at the phase transition, i.e. p=1/n, the largest component satisfies a power-law of order 2/3.
For which d-regular graphs does percolation with p=1/(d-1) exhibit similar "mean-field" behavior? We show that this occurs for graphs where the probability of a non-backtracking random walk to return to its initial location behaves as it does on the complete graph. In particular, the celebrated Lubotzky-Phillips-Sarnak expander graphs and Cartesian products of 2 or 3 complete graphs exhibit mean-field behavior at p=1/(d-1); surprisingly, a product of 4 complete graphs does not.
--------------------------------------------------------------------------
Bernhard
Haak, Universite Bordeaux, On
Carleson measure criteria in linear systems theory
----------------------------------------------------------------------------
Gidi Amir,
We study an exclusion process on Z where
each particle is assigned a class (number in Z) and each particle tries to swap
places with its right neighbor with rate 1 if that neighbor has a higher class
number. (Alternatively, each edge of Z
is "sorted" with rate 1) With the right starting conditions,
the position of each particle (normalized by the time) converges to a constant
speed. The speed of each particle is uniform in [-1,1], but there are strong dependencies between the
behavior of different particles. We study this exclusion process and the
distribution of its related speed process. In particular we show the existence
of infinite "convoys" – particles (with different classes) all
converging to the same speed. We also give some new symmetries for the
multi-type tasep. Some of our results apply also to
the partially asymmetric case as well.
This is joint work-in-progress with Omer
Angel and Benedek Valko
from the
All definitions will be given in the
lecture.
No prior knowledge of exclusion processes is
assumed.
---------------------------------------------------------------------------------------
Jonathon Peterson, University of Minnesote, Quenched
limits for a one-dimensional random walk in random environment.
Abstract: In 1975 Kesten,
Kozlov, and Spitzer analyzed the annealed
(averaged) limiting distributions for
one-dimensional transient random
walks in random environments (RWRE). In
particular they showed that the
annealed limiting distributions are related
to the stable distritions. In
this talk, I will analyze the quenched
(conditioned on the environment)
limiting distributions. Somewhat
surprisingly, the quenched behavior can
be
very different from the annealed behavior. In particular, for certain
laws
on environments there are no quenched limiting distributions.
-----------------------------------------------------------------------
NOTE special TIME:
Wednesday,
Yuval
Peres, Microsoft Research, Compression exponents of amenable groups and escape rates of random walks
Abstract: Let G be a countable amenable
group, equipped with a finite set of generators and a corresponding word metric
$d(x,y)$. The
Hilbert-space compression exponent $a_*$ of G is the supremum
of all $a>0$ such that there exists a Lipschitz
map $f$ from G to Hilbert space and a constant $c>0$ so that for all $x,y$ in G, the norm $||f(x)-f(y)||$ is at least $cd(x,y)^a.$ Let $b$ denote the
escape rate exponent for simple random walk (X_t) on
the Cayley graph of G, that is, suppose that
$Ed(X_0,X_t)$ grows like $t^b$. We prove that $2ba_*$
is at most $1$, and equality holds in many cases. In particular, for the wreath product of the
integer lattice $Z$ with itself, it was known that $b=3/4$, and we show that
$a_*=2/3$. A key open question is
whether the identity $2ba_*=1$ holds for all finitely-generated amenable
G. (It is not even known whether $a_*$
is always at least $1/2$). Our proof uses K. Ball's notion of Markov type for
metric spaces. We also obtain extensions to $L^p$
compression via p-stable random walks. (Joint work with Assaf
Naor and Tim Austin).
-----------------------------------------------------------------------------------------
February 28, 2008,
Ilya Goldsheid, University of London, RWRE on a strip, products of random
transformations, and Lyapunov exponents
Abstract. The study of asymptotic properties
of random walks (RW) in random environments (RE) on a strip of width $m$ can be
naturally reduced to that of products of random transformations of the set of
$m\times m$ stochastic matrices. In my talk, I shall explain several recent
(and relatively recent) results obtained via this approach. They extend to the
strip case some of the classical theorems of Kesten-Kozlov-Spitser
(1975), as well as the Sinai $(\log t)^2$ asymptotic behaviour
(1982) which were proved for simple one-dimensional RWRE.
-------------------------------------------------------------------
February 7, 2008,
--------------------------------------------------------------------
NOTE special TIME and VENUE:
Wednesday, January 30, 2008,
16:00-18:00, Lecture room 5 at
Erwin Bolthausen,
University of Zurich, A fixed-point
proof of central limit theorems for certain convolution equations
---------------------------------------------------------------------
NOTE special TIME and VENUE:
Wednesday, January 23, 2008, 16:00-18:00,
Lecture room 5 at
Jay Rosen, City
University of New York, Existence
of a critical point for the infinite divisibility of squared Gaussian vectors
Abstract: Let (G_1,\ldots, G_n) be a mean zero Gaussian vector in R^n
with covariance matrix \Gamma. Necessary
and sufficient conditions for the infinite divisibility of
(G^2_1,\ldots, G^2_n) in terms of \Gamma have been known for some time. More
recent results of Eisenbaum and Kaspi
give necessary and sufficient
conditions in terms of \Gamma for
((G_1+r)^2,\ldots, (G_n+r)^2)
to be the infinitely divisible for all real r.
This is related to the local times of an associated Markov process. We
show that for certain \Gamma there exists a critical r_0>0 such that
((G_1+r)^2,\ldots, (G_n+r)^2)
is infinitely divisible for all |r|\leq r_0 but not
for |r|>r_0. Joint work with Michael Marcus.
--------------------------------------------------------------------
January 17 + 24, 2008
The following question could have appeard in a calculus undergraduate textbook. Consider
continuous real-valued functions defined on a set of reals
X. Is it true that:
(*) Whenever the functions f_n converge pointwise to 0,
there are positive reals
epsilon_n converging to 0,
such that for each x in X, |f_n(x)|<epsilon_n for almost
all n?
The answer is "Yes" if X is
countable, and "No" if X is the entire real line. For which X is the
answer positive?
The concept (*) is motivated by studies in
Harmonic analysis, involving sets of uniqueness for trigonometric series. (We
will not give details about that.)
Another concept, due to Arhangelskii,
comes from the question whether a product of Fr'echet
spaces is Fr'echet, and involves a natural
amalgamation of a sequence of convergent sequences of functions. Recently, Bukovsky-Hales and independently Sakai proved that this
concept coincides with (*) above, which makes our question doubly interesting.
We will try to give a complete proof of a
result that took us very long to believe:
(*) holds if, and only if, each Borel image of X in the Baire
space is bounded (with respect to eventual dominance).
This implies a solution of a variety of
problems posed in the literature. In fact, we are not aware of any problem
concerning these concepts which remains open in light of this result. It also
has an application to a question on approximating discontinuous functions by
continuous ones, and a question whose positive solution would lead to a
solution of a rather old problem of Vinokurov.
Two GFAP meetings will be dedicated to this
work, so that all required definitions will be given, as well as the details of
the main proofs.
This is a very recent joint work with Lyubomyr Zdomskyy.
------------------------------------------------------------------------------------
NOTE special TIME and VENUE:
Wednesday, January 16, 2008,
16:00-18:00, Lecture room 5 at
Atilla Yilmaz, New York University, Large deviations for random walk in a random environment
Random walk in a random environment is a
discrete time Markov chain on $\mathbb{Z}^d$ with
random transition probabilities $\pi(x,x+y)$. The
collection $\omega = (\pi(x,x+y))_{x,y}$ is the called the environment. If $(X_n)_n$ denotes the path of the``particle",
$(T_{X_n}\omega)_n$ is a Markov chain on the space of
environments $\Omega$. Here, $T$ denotes the spatial shift on $\Omega$ and the
chain is called the ``environment Markov chain". This approach, known as
taking the point of view of the particle, is standard in the study of random
media.
In this talk, I will ask the following vague
question: ``Conditioned on the particle having asymptotic velocity equal to a
given atypical vector, how does the environment Markov chain behave?". My
answer to various rigorous formulations of this question will involve equality
of quenched and averaged rates in some cases, Doob
transforms, level-2 large deviation principles, and minimizers
of certain variational formulae.
------------------------------------------------------------------------
January 10, 2008,
NOTE special TIME
December
27, 2007,
One of the main questions that arise when studying
random and quasi-random structures is which properties P are such that any
object that satisfies P ``behaves'' like a truly random one. In the context of
graphs, Chung, Graham, and Wilson call a graph p-quasi-random if it satisfies a
long list of properties that hold in G(n,p) with high
probability, like edge distribution, spectral gap, cut size, and more.
Our main result here is that the following
holds for *any* fixed graph H: if a graph G has the property that the
distribution of induced copies of H in a graph G is close (in a well defined
way) to the distribution we would expect to have in G(n,p),
then G is either p-quasi-random or q-quasi-random, for some q=q(p,H). In other words, having the correct distribution of
induced copies of any single graph H, is enough to guarantee that a graph has
all the properties of a random one.
The talk will be self contained and will not
assume any prior knowledge.
Joint work with Raphy
Yuster
NOTE special TIME and VENUE:
Wednesday, December 26, 2007, 16:00-18:00, Lecture room 1.
Oded Schramm, Microsoft Research, Testing graphs for planarity
Abstract: Suppose that you can sample
vertices in a big graph and ask about their neighbors. Your task is to decide
with as few questions as possible if the graph satisfies some property. Given
an a priori bound on the vertex degrees and given a positive s, we show that
with a bounded number of queries you can distinguish between planar graphs and
graphs that are s-far from being planar (in an appropriate sense). The testing
procedure is randomized and has some chance of failing, but the probability of
an incorrect answer can be made arbitrarily small, regardless of the graph
being tested. A similar result holds for all minor-closed properties. This is
joint work with
NOTE
slight change in TIME
December
13, 2007,
Robert Krauthgmaer
, Weizmann Institute, On embedding edit distance into L_1
The edit distance (aka
Levenshtein distance) between two strings is the
number of character insertions, deletions and substitutions required to
transform one string to the other. A very powerful paradigm for solving
computational problems on the metric space induced by the edit distance is to
embed this metric into L_1, using a low-distortion map (if possible).
I will first
present a low-distortion embedding of edit distance on permutations (aka the Ulam metric) [based on
joint work (i) with Moses Charikar,
and (ii) with Parikshit Gopalan
and T.S. Jayram]. I will then discuss lower bounds on
the distortion required to embed edit distance on 0-1 strings [joint work with
Yuval Rabani] and, more briefly, on permutations
[joint work with Alex Andoni].
A simple random walk (SRW) on a graph is a
Markov chain whose state space is the vertex set and the next state
distribution is uniform among the neighbors of the current state. A graph is called recurrent
if a SRW on it returns to the starting vertex with probability 1, and called
transient otherwise. The path of a walk on a graph is simply the set of edges
this walk has traversed.
Our main result is that the path of a SRW on
any graph is a recurrent graph. The proof uses the electrical network
interpretation of random walks.
We will give a sketch of the proof,
including the necessary background, and discuss related questions and
conjectures.
Based on joint works with Itai Benjamini, Russell Lyons and
Oded Schramm.
We
consider the problem of embedding vectors from an arbitrary
Euclidean space into a low dimensional Euclidean space, while
preserving up to a small distortion, a subset of the distances. In
particular, preserving only the distance of each vector to a small
number of its nearest neighbors. We show that even when the subset
of distances we wish to preserve is very small, the problem does
not become easier than when one requires to preserve all the
distances.
Joint work with Gideon Schechtman.
Concentration of measure is a fundamental phenomenon in
high-dimensional geometry with far-reaching applications in fields
such as probability theory, functional analysis, computer science,
statistics, and machine learning.
Concentration bounds for non-product, non-Haar measures are fairly
recent: the first such result was obtained for contracting Markov
chains by Marton in 1996. Since then, several other such results have
been proved; with few exceptions, these rely on coupling techniques.
Though coupling is of unquestionable utility as a theoretical tool,
it appears to have some limitations. Coupling has yet to be used to
obtain bounds for more general Markov-type processes: hidden (or
partially observed) Markov chains, Markov trees, etc. As an
alternative to coupling, we apply the elementary Markov contraction
lemma in a novel way, to obtain simple, useful, and apparently
new concentration results for the various Markov-type processes. Our
technique is generic and holds the potential to yield numerous
results in this vein.
This talk is intended for a broad mathematical audience:
background, definitions, and motivation will be provided.
Christophe Garban, Universite Paris-Sud & ENS Paris, The
Fourier Spectrum of critical
percolation
The indicator function for the existence of
a percolation crossing in an n by n square can be seen as a function on the
discrete cube $\{-1,1\}^E$, where $E$ is the set of edges. As such, it admits a
``Fourier'' expansion. In a joint work with Gabor
Pete and Oded Schramm, we obtain sharp estimates for
the ``weight'' of the Fourier coefficients at different frequencies. This good undertsanding of the spectrum has nice consequences for the
model of dynamical percolation. For instance, we can prove in the case of the
triangular lattice that the dimension of exceptional times is 31/36, and in the
Z^2 case, we can prove the existence of such exceptional times.
Pierre Nolin, Ecole Normale Supérieure
& Université Paris-Sud,
Some properties of near-critical
percolation
In two dimensions, a precise description of percolation at the critical
point was made possible by Schramm’s SLE processes, studied by Lawler, Schramm
and Werner, and by Smirnov’s proof of conformal invariance. Combined with
Kesten’s scaling results, this description then
provides a good picture of near-critical percolation, for instance the critical
exponents describing the main characteristic functions (such as the density of
the infinite cluster or the characteristic length).
We will discuss the off-critical regime, in particular the possible
scaling limits. Even if they are not conformal invariant, it seems natural to
try to relate them to SLE(6): we will show that they actually share the same
exponents and dimension properties. However, they also are
“locally” asymmetric, on every scale, so that their laws turn out
to be singular with respect to that of SLE(6). This is joint work with Wendelin Werner.
For previous years see:
http://www.cs.biu.ac.il/~tsaban/gfap.html
and
http://www.wisdom.weizmann.ac.il/mathusers/gideon/seminar.html