Thursday 13:30-15:30, Ziskind 155 map, directions.

To suggest a talk (yours or somebody else's) contact Ronen Eldan, Itai Benjamini, Gady Kozma or Gideon Schechtman.

To join the mailing list, contact Amir Gonen (amir.gonen@weizmann.ac.il). This seminar also has a google calendar entry: Weizmann - GFAP Seminar  (Geometric Functional Analysis and Probability)

Upcoming talks

Mar 19th, 2020

Itay Glazer (WIS)

On families of random walks induced by word maps

Given a word w, i.e. an element of a free group F_r on a set of r elements, and a finite group G, one can associate a word map w:G^r-->G. Such a word map induces a natural probability measure on G, and varying over different families of finite groups, we can study the corresponding family of random walks. We focus on families of the form {SLn(Fp)} and {SLn(Z/p^kZ)}. It turns out that various mixing properties of these random walks have an algebro-geometric characterization in terms of certain singularity properties of the polynomial maps w:SLn(C)^r-->SLn(C). We discuss this characterization, and present various results on these random walks. This kind of problems can be viewed as probabilistic and algebro-geometric analogues of the classic Waring problem. The talk is self contained, and no prior knowledge in algebraic geometry is assumed. Based on a joint project with Yotam Hendel.

Mar 26th, 2020

Remco van der Hofstad (Eindhoven) - CANCELLED

TBA

List of previous talks sorted backwards

Mar 5th, 2020

Emanuel Milman (Technion) + Tal Orenshtein (Berlin)

Emanuel Milman: Functional Inequalities on sub-Riemannian manifolds via QCD

We are interested in obtaining Poincar\’e and log-Sobolev inequalities on domains in sub-Riemannian manifolds (equipped with their natural sub-Riemannian metric and volume measure). It is well-known that strictly sub-Riemannian manifolds do not satisfy any type of Curvature-Dimension condition CD(K,N), introduced by Lott-Sturm-Villani some 15 years ago, so we must follow a different path. We show that while ideal (strictly) sub-Riemannian manifolds do not satisfy any type of CD condition, they do satisfy a quasi-convex relaxation thereof, which we name QCD(Q,K,N). As a consequence, these spaces satisfy numerous functional inequalities with exactly the same quantitative dependence (up to a factor of Q) as their CD counterparts. We achieve this by extending the localization paradigm to completely general interpolation inequalities, and a one-dimensional comparison of QCD densities with their “CD upper envelope”. We thus obtain the best known quantitative estimates for (say) the L^p-Poincar\’e and log-Sobolev inequalities on domains in the ideal sub-Riemannian setting, which in particular are independent of the topological dimension. For instance, the classical Li-Yau / Zhong-Yang spectral-gap estimate holds on all Heisenberg groups of arbitrary dimension up to a factor of 4. No prior knowledge will be assumed, and we will (hopefully) explain all of the above notions during the talk.

Tal Orenshtein: Rough walks in random environment.

In this talk we shall review scaling limits for random walks in random environment lifted to the rough path space to the enhanced Brownian motion. Except for the immediate application to SDEs, this adds some new information on the structure of the limiting path. Time permitted, we shall elaborate on the tools to tackle these problems. Based on joint works with Olga Lopusanschi, with Jean-Dominique Deuschel and Nicolas Perkowski and with Johaness B?umler, Noam Berger and Martin Slowik.

Feb 13th, 2020

Anirban Basak (ITCS)

Upper tail large deviations of subgraph counts in sparse random graphs

For a $\Delta$-regular connected graph ${\sf H}$ the problem of determining the upper tail large deviation for the number of copies of ${\sf H}$ in an Erd\H{o}s-R\'{e}nyi graph on $n$ vertices with edge probability $p$ has generated significant interests. In the sparse regime, i.e. for $p \ll 1$, when $np^{\Delta/2} \gg (\log n)^{1/(v_{\sf H}-2)}$, where $v_{\sf H}$ is the number of vertices in ${\sf H}$, the upper tail large deviation event is believed to occur due to the presence of localized structures. Whereas, for $p$ below the above threshold the large deviation is expected to be given by that of a Poisson random variable. In this talk, we will discuss some progress in resolving this conjecture. This is based on joint work with Riddhipratim Basu.

Jan 30th, 2020

Amir Yehudayoff (Technion)

Anti-concentration of inner products

The plan is to discuss anti-concentration of the inner product between two independent random vectors in Euclidean space. We shall go over some background and applications, and see some proofs.

Jan 23rd, 2020

James Lee (University of Washington)

Metric entropies, L_1 transportation, and competitive analysis

The MTS problem (Borodon, Linial, and Saks 1992) is a general model for the analysis of algorithms that optimize in the presence of information arriving over time, where the state space is equipped with a metric. I will discuss a relatively new approach to this area, where both the algorithm and method of analysis are derived canonically from a choice of a "regularizer" on the probability simplex. The regularizer can be interpreted as a Riemannian structure on the simplex, and then the algorithm is simply a gradient flow. Defining the regularizer as an appropriate "noisy" multiscale metric entropy (similar to, e.g., the Talagrand \gamma_1 functional) yields the best-known competitive ratio for every metric space. For ultrametrics (aka, "HST metrics"), this achieves the conjectured bound, but the algorithm falls short of resolving the MTS conjecture for many other spaces, including subsets of the real line.

Jan 9th, 2020

Abel Farkas

The Geometric measure theory of the Brownian path

Let B denote the range of the Brownian motion in R^d. For a deterministic Borel a measure nu we wish to find a random measure mu such that the support of mu is contained in B and the expectation of mu is nu. We discuss when exactly can there be such a random measure and construct in those cases. We establish a formula for the expectation of the double integral with respect to mu, which is a strong tool for the geometric measure theory of the Brownian path.

Dec 26th, 2019

Max Fathi (Toulouse & CNRS)

A new proof of the Caffarelli contraction theorem

The Caffarelli contraction theorem states that the Brenier optimal transport map sending the Gaussian measure onto a uniformly log-concave probability measure is lipschitz. In this talk, I will present a new proof, using entropic regularization and a variational characterization of lipschitz transport maps due to Gozlan and Juillet. Based on joint work with Nathael Gozlan and Maxime Prod’homme.

Jan 2nd, 2020

Dima Dolgopyat

Edgeworth expansion in Central Limit Theorem

It is well known that Central Limit Theorem is very effective giving a reasonable approximation for sums of a quite small number of terms. Edgeworth expansions provide a convenient way to control the error in the Central Limit Theorem. In this talk I will review some recent results on this subject related to the interface between probability and dynamics.  

Dec 19th, 2019

Esty Kelman (TAU) + Asaf Katz (Chicago)

Esty Kelman: Boolean Functions and Their Effective Degree

The KKL Theorem (there is always a significantly influential variable)  is sometimes tight as in the Tribes functions, but many times is not tight as in the Majority function. We propose a generalized version of KKL, with a new parameter -  the effective degree, which replaces the role of the average degree in the KKL statement. This allows us to prove a tight result for many cases shows how large the influence of the most influential variable is. We generalize KKL in another manner finding a significantly influential variable within a subset of variables.  This generalization, in turn, implies a generalized version of Friedgut Junta Theorem. If time allows, we will see how easily our Theorem implies the Friedgut Junta Theorem and stronger Junta results.

Asaf Katz: Measure rigidity for Anosov flows via the factorization method

We show how the factorization method, pioneered by Eskin and Mirzakhani in their groundbreaking work about measure classification for the moduli space of translation surfaces, can be adapted to smooth ergodic theory.Using this adaption, we show that for a quantitatively non-integrable Anosov flow, every generalized u-Gibbs measure is absolutely continuous with respect to the whole unstable manifold.

Dec 12th, 2019

Naomi Feldheim (BIU)

Existence of persistence exponent for Gaussian stationary functions

Let $Z(t)$ be a Gaussian stationary function on the real line, and fix a level $L>0$. We are interested in the asymptotic behavior of the persistence probability: $P(T) = P( Z(t) > L$, for all $t \in [0,T]$ ). One would guess that for "nice processes", the behavior of P(T) should be exponential. For non-negative correlations this may be established via sub-additivity arguments. However, so far, not a single example with sign-changing correlations was known to exhibit existence of the limit of $\log P(T)}/T$, as $T$ approaches infinity (that is, to have a true "persistence exponent"). In the talk I will present a proof of existence of the persistence exponent, for processes whose spectral measure is monotone on $[0,\infty)$ and is continuous and non-vanishing at 0. This includes, for example, the sinc-kernel process (whose covariance function is $sin(t)/t$ ). Joint work with Ohad Feldheim and Sumit Mukherjee.

Nov 28th, 2019

Amir Dembo (Stanford) + Alexander Fish (Sydney)

Amir Dembo: Dynamics for spherical spin glasses: Disorder dependent initial conditions

In this talk, based on a joint work with Eliran Subag, I will explain how to rigorously derive the integro-differential equations that arise in the thermodynamic limit of the empirical correlation and response functions for Langevin dynamics in mixed spherical p-spin disordered mean-field models. I will then compare the large time asymptotic of these equations in case of a uniform (infinite-temperature) starting point, to what one obtains when starting within one of the spherical bands on which the Gibbs measure concentrates at low temperature, commenting on the existence of an aging phenomenon, and on the relations with the recently discovered geometric structure of the Gibbs measures at low temperature.

Alexander Fish: Finite configurations in trees of positive growth rate

We will talk on the relation between the abundance of finite configurations that we observe in trees and their growth rate. We will survey the Furstenberg-Weiss correspondence principle which relates a tree of positive growth rate with Markov process, and subsequently provides a quantitative relationship between the density of a finite subtree that appears in the tree with a quantity defined on the Markov space and which can be estimated by use of ergodic methods. We will sketch a proof of one direct and one inverse theorem relating the abundance of certain finite configurations and the growth rate of a tree. Some open problems related to this work will be discussed. Based on a joint work with Leo Jiang (Toronto).

Nov 14th, 2019

Jonathan Hermon (Cambridge)

Random Cayley graphs

We consider the random Cayley graph of a finite group $G$ formed by picking $k$ random generators uniformly at random: (1) We prove universality of cutoff (for the random walk) and a concentration of measure phenomenon in the Abelian setup (namely, that all but $o(|G|)$ elements lie at distance $[R-o(R),R-o(R)]$ from the origin, where $R$ is the minimal ball in $Z^k$ of size at least $|G|$), provided $k \gg 1$ is large in terms of the size of the smallest generating set of $G$. As conjectured by Aldous and Diaconis, the cutoff time is independent of the algebraic structure (it is given by the time at which the entropy of a random walk on $Z^k$ is $\log|G|$). (2) We prove analogous results for the Heisenberg $H_{p,d}$  groups  of  $d \times d$ uni-upper triangular matrices with entries defined mod $p$, for $p$ prime and $d$ fixed or diverging slowly. (3) Lastly, we resolve a conjecture of D. Wilson that if $G$ is a group of size at most $2^d$ then for all $k$ its mixing time in this model is as rapid as that of $Z_2^d$ and likewise, that the slowest mixing $p$-group of a given size is $Z_p^d$. (Joint work with Sam Thomas.)

Oct 31th, 2019

Mikhail Ostrovskii (St. John’s University, New York, USA)

Geometry of transportation cost (a.k.a. Earth Mover or Wasserstein distance)

We consider (finitely supported) transportation problems on a metric space M. They form a vector space TP(M). The optimal transportation cost for such transportation problems is a norm on this space. This normed space is of interest for the theory of metric embeddings because the space M embeds into it isometrically. I am going to talk about geometry of such normed spaces. The most important questions for this talk are relations of these spaces with $L_1$ and $L_\infty$ spaces.

Oct 24th, 2019

Sergey Bobkov (U Minnesota)

Transport bounds for empirical measures

We will be discussing a Fourier-analytic approach to optimal matching between independent samples, with an elementary proof of the Ajtai-Komlos-Tusnady theorem. The talk is based on a joint work with Michel Ledoux.

July 11th, 2019

Shamgar Gurevich (Madison)

Harmonic Analysis on GL_n over finite fields.

here are many formulas that express interesting properties of a finite group G in terms of sums over its characters. For evaluating or estimating these sums, one of the most salient quantities to understand is the {\it character ratio}: $trace(\rho(g))/dim(\rho)$, for an irreducible representation $\rho$ of G and an element g of G. For example, Diaconis and Shahshahani stated a formula of the mentioned type for analyzing certain random walks on G. Recently, we discovered that for classical groups G over finite fields there is a natural invariant of representations that provides strong information on the character ratio. We call this invariant rank. This talk will discuss the notion of rank for GLn over finite fields, and explain how one can apply the results to verify mixing time and rate for certain random walks. The talk will assume basic notions of linear algebra in Hilbert spaces, and the definition of a group. This is joint work with Roger Howe (Yale and Texas AM).

July 25th, 2019

Jonathan Hermon (Cambridge)

Anchored expansion in supercritical percolation on nonamenable graphs.

Let G be a transitive nonamenable graph, and consider supercritical Bernoulli bond percolation on G. We prove that the probability that the origin lies in a finite cluster of size n decays exponentially in n. We deduce that: 1. Every infinite cluster has anchored expansion almost surely. This answers positively a question of Benjamini, Lyons, and Schramm (1997). 2. Various observables, including the percolation probability and the truncated susceptibility are analytic functions of p throughout the entire supercritical phase. Joint work with Tom Hutchcroft.

July 4th, 2019

Eviatar Procaccia (Texas A&M)

Stationary Hastings-Levitov model

We construct and study a stationary version of the Hastings-Levitov(0) model. We prove that unlike the classical model, in the stationary case particle sizes are constant in expectation, yielding that this model can be seen as a tractable off-lattice Diffusion Limited Aggregation (DLA). The stationary setting together with a geometric interpretations of the harmonic measure yields new geometric results such as stabilization, finiteness of arms and unbounded width in mean of arms. Moreover we can present an exact conjecture for the fractal dimension.

June 20th, 2019

Mark Rudelson (UMich) + Serguei Popov (IMECC)

Consider a sequence of $n$ by $n$ random matrices $A_n$ whose entries are independent identically distributed random variables. The circular law asserts that the distribution of the eigenvalues of properly normalized matrices $A_n$ converges to the uniform measure on the unit disc as $n$ tends to infinity. We prove this law for sparse random matrices under the optimal sparsity assumption. Joint work with Konstantin Tikhomirov.

We consider the two-dimensional simple random walk conditioned on never hitting the origin. This process is a Markov chain, namely, it is the Doob $h$-transform of the simple random walk with respect to the potential kernel. It is known to be transient and we show that it is ``almost recurrent'' in the sense that each infinite set is visited infinitely often, almost surely. We prove that, for a "typical large set", the proportion of its sites visited by the conditioned walk is approximately a Uniform$[0,1]$ random variable. Also, given a set $G\subset\R^2$ that does not "surround" the origin, we prove that a.s.\ there is an infinite number of $k$'s such that $kG\cap \Z^2$ is unvisited. These results suggest that the range of the conditioned walk has "fractal" behavior. This is a joint work with Nina Gantert and Marina Vachkovskaia, see arxiv.org/abs/1804.00291 Also, there is much more about conditioned walks in my new book (www.ime.unicamp.br/~popov/2srw.pdf, work in progress). Comments and suggestions on the latter are very welcome!

June 6th, 2019

Yotam Smilansky (HUJI)

We consider statistical questions concerning colored sequences of partitions, produced by applying a partition process which was first introduced by Kakutani for the 1-dimensional case. This process can be generalized as the application of a fixed multiscale substitution rule, defined on a finite set of colored sets in R^d, on elements of maximal measure in each partition. Colored sets appearing in the sequence are modeled by certain flows on an associated directed weighted graph, and natural statistical questions can be reformulated as questions on the distribution of paths on graphs. Under some incommensurability assumptions, we show that special properties of Laplace transforms of the relevant counting functions imply explicit statistical results.

May 16th, 2019

7th Student Probability Day

May 23rd, 2019

Gregory Berkolaiko (Texas A&M)

Understanding statistical properties of zeros of Laplacian eigenfunctions is a program which is attracting much attention from mathematicians and physicists. We will discuss this program in the setting of "quantum graphs", self-adjoint differential operators acting on functions living on a metric graph. Numerical studies of quantum graphs motivated a conjecture that the distribution of nodal surplus (a suitably rescaled number of zeros of the n-th eigenfunction) has a universal form: it approaches Gaussian as the number of cycles grows. The first step towards proving this conjecture is a result established for graphs which are composed of cycles separated by bridges. For such graphs we use the nodal-magnetic theorem of the speaker, Colin de Verdiere and Weyand to prove that the distribution of the nodal surplus is binomial with parameters p=1/2 and n equal to the number of cycles. Based on joint work with Lior Alon and Ram Band.

April 18th, 2019

Michal Strzelecki (Warsaw)

On modified log-Sobolev inequalities

In order to prove concentration estimates for (products of) measures with heavier tails than the standard Gaussian measure one can use several variants of the classical log-Sobolev inequality, e.g., Beckner-type inequalities of Latala and Oleszkiewicz or modified log-Sobolev inequalities of Gentil, Guillin, and Miclo. The main result I plan to present asserts that a probability measure on R^d which satisfies the former inequality satisfies also the latter. Based on joint work with Franck Barthe.

April 11th, 2019

Lisa Hartung (Mainz)

From 1 to 6 in branching Brownian motion

Brownian motion is a classical process in probability theory belonging to the class of ‘Log-correlated random fields'. It is well known do to Bramson that the order of the maximum has a different logarithmic correction as the corresponding independent setting. In this talk we look at a version of branching Brownian motion where we slightly vary the diffusion parameter in a way that, when looking at the order of the maximum, we can smoothly interpolate between the logarithmic correction for independent random variables ($\frac{1}{2\sqrt 2}\ln(t)$) and the logarithmic correction of BBM ($\frac{3}{2\sqrt 2}\ln(t)$) and the logarithmic correction of 2-speed BBM with increasing variances ($\frac{6}{2\sqrt 2}\ln(t)$). We also establish in all cases the asymptotic law of the maximum and characterise the extremal process, which turns out to coincide essentially with that of standard BBM. We will see that the key to the above results is a precise understanding of the entropic repulsion experienced by an extremal particle. (joint work with A. Bovier)

Mar 21st, 2019

Zemer Kosloff (HUJI)

On the local limit theorem in dynamical systems

In 1987, Burton and Denker proved the remarkable result that in every aperiodic dynamical systems (including irrational rotations for example) there is a square integrable, zero mean function such that its corresponding time series satisfies a CLT. Subsequently, Volny showed that one can find a function which satisfies the strong (almost sure) invariance principle. All these constructions resulted in a non-lattice distribution. In a joint work with Dalibor Volny we show that there exists an integer valued cocycle which satisfies the local limit theorem. The first hour will involve painting (Rokhlin towers) while the second one will be mainly concerned with the proof of the local CLT.

Mar 28th, 2019

Ami Viselter (Haifa)

Convolution semigroups and generating functionals on quantum groups

The theory of locally compact quantum groups grew out of the need to extend Pontryagin's duality for locally compact abelian groups to a wider class of objects, as well as from a modern "quantum" point of view suggesting the replacement of some algebras of functions on a group by non-commutative objects, namely operator algebras. In this talk, which will be split into two parts, we will show how several fundamental notions from probability and geometric group theory fit in this framework. The first part will be an introduction to locally compact quantum groups. We will present the rationale and the definitions, give examples, and explain how the theory is related to other branches of math. If time permits, we will also touch upon more specific notions related to the second part. In the second part we will discuss convolution semigroups of states, as well as generating functionals, on locally compact quantum groups. One type of examples comes from probability: the family of distributions of a L\'evy process form a convolution semigroup, which in turn admits a natural generating functional. Another type of examples comes from (locally compact) group theory, involving semigroups of positive-definite functions and conditionally negative-definite functions, which provide important information about the group's geometry. We will explain how these notions are related and how all this extends to the quantum world; derive geometric characterizations of two approximation properties of locally compact quantum groups; see how generating functionals may be (re)constructed and study their domains; and indicate how our results can be used to study cocycles. Based on joint work with Adam Skalski. No background in operator algebras will be assumed.

Mar 14th, 2019

Marta Strzelecka (Warsaw)

On k-maxima of log-concave vectors

Mar 7th, 2019

Ori Gurel Gurevich (HUJI)

Random walks on planar graphs

We will discuss several results relating the behavior of a random walk on a planar graph and the geometric properties of a nice embedding of the graph in the plane (specifically, circle packing of the graph). One such a result is that for a bounded degree graph, the simple random walk is recurrent if and only if the boundary of the nice embedding is a polar set (that is, Brownian motion misses it almost surely). If the degrees are unbounded, this is no longer true, but for the case of circle packing of a triangulation, there are weights which are obtained naturally from the circle packing, such that when the boundary is polar, the weighted random walk is recurrent (we believe the converse also hold). These weights arise also in the context of discrete holomorphic and harmonic functions, a discrete analog of complex holomorphic functions. We show that as the sizes of circles, or more generally, the lengths of edges in the nice embedding of the graph tend to zero, the discrete harmonic functions converge to their continuous counterpart with the same boundary conditions. Equivalently, that the exit measure of the weighted random walk converges to the exit measure of standard Brownian motion. This improves previous results of Skopenkov 2013 and Werness 2015, who proves similar results under additional local and global assumptions on the embedding. In particular, we make no assumptions on the degrees of the graph, making the result applicable to models of random planar maps. Based of joint works with Daniel Jerison, Asaf Nachmias, Matan Seidel and Juan Souto.

Feb 28th, 2019

Fanny Augeri (WIS) + Elliot Paquette (Ohio)

Fanny Auegei: Nonlinear large deviations bounds with applications to sparse Erdos-Renyi graphs.

In this talk, I will present the framework of the so-called nonlinear large deviations introduced by Chatterjee and Dembo. In a seminal paper, they provided a sufficient criterion in order that the large deviations of a function on the discrete hypercube to be due by only changing the mean of the background measure. This sufficient condition was formulated in terms of the complexity of the gradient of the function of interest. I will present general nonlinear large deviation estimates similar to Chatterjee-Dembo's original bounds except that we do not require any second order smoothness. The approach relies on convex analysis arguments and is valid for a broad class of distributions. Then, I will detail an application of this nonlinear large deviations bounds to the problem of estimating the upper tail of cycles counts in sparse Erdos-Renyi graphs down to the connectivity parameter $n^{-1/2}$.

Elliot Paquette: The Gaussian analytic function is either bounded or covers the plane.

The Gaussian analytic function (GAF) is a power series with independent Gaussian coefficients. In the case that this power series has radius of convergence 1, under mild regularity assumptions on the coefficients, it is a classical theorem that the power series is a.s. bounded on open disk if and only if it extends continuously to a function on the closed unit disk a.s. Nonetheless, there exists a natural range of coefficients in which the GAF has boundary values in L-p, but is a.s. unbounded. How wild are these boundary values? Well, Kahane asked if a GAF either a.s. extends continuously to the closed disk or a.s. has range covering the whole plane. We show partial progress in establishing this in the affirmative. Joint with Alon Nishry.

Feb 21st, 2019

Houcein Abdalaoui (Rouen)

On Banach problem and simple Lebesgue spectrum.

Following Ulam, Banach asked on the existence of dynamical system on real line with simple Lebesgue spectrum. I discuss the connection of this problem to the famous Banach problem in ergodic theory due essentially to Rohklin. I will further present my recent contribution to this problem and the connection to so called Erd?s flat polynomials problem in Harmonic analysis due to J. Bourgain . My talk is based on my recent work and joint work with Mahendra Nadkarni (CBS Mumbai, India).

Feb 14th, 2019

Rafael Butez (WIS)

On the extremal particles of a Coulomb gas and random polynomials

The purpose of this talk is to understand the behavior of the extremal zeros of random polynomials of the form $ P_N(z) = \sum_{k=0}^{N} a_k R_k(z)$ where the family $(R_k)_{k \leq N}$ is an orthonormal basis for the scalar product $\langle P,Q \rangle = \int P(z) \overline{Q(z)} e^{-2N V^{\nu(z)}} d\nu(z)$ with $\nu$ a radial probability measure on $\CC$ and $V^{\nu}(z)= \int \log |z-w|d\nu(w)$. Although the zeros of these polynomials spread like the measure $\nu$, the zeros of maximum modulus lie outsite of the support. More precisely, the point process of the roots outside of the support of the equilibrium measure converges towards the Bergman point process of the complement of the support. We also study similar results on a model of Coulomb gases in dimension $2$ where the confining potential is generated by the presence of a fixed background of positive charges. If $\nu$ is a probability measure, we study the system of particles with joint distribution on $\CC^N$, $\frac{1}{Z_N} \prod_{i \leq j} |x_i-x_j|^2 e^{-2(N+1)\sum_{k=1}^{N}V^{\nu}(x_k)} d\ell_{\CC^N}(x_1,\dots,x_N).$ This model in closely related to the study of the zeros of random polynomials. We show that the extremal particles of this Coulomb gas present a similar behavior to the random polynomial setting. All the results mentioned above are done in collaboration with David Garcia-Zelada.

Jan 31st, 2019

Dan Mikulincer (WIS)

Quantitative high-dimensional CLTs via martingale embeddings

We introduce a new method for obtaining quantitative convergence rates for the central limit theorem (CLT) in the high dimensional regime. The method is based on the notion of a martingale embedding, a multivariate analogue of Skorokhod's embedding. Using the method we are able to obtain several new bounds for convergence in transportation distance and in entropy, and in particular: (a) We improve the best known bound, for convergence in quadratic Wasserstein transportation distance for bounded random vectors; (b) We derive a non-asymptotic convergence rate for the entropic CLT in arbitrary dimension, for log-concave random vectors; (c) We give an improved bound for convergence in transportation distance under a log-concavity assumption and improvements for both metrics under the assumption of strong log-concavity. In this talk, we will review the method, and explain how one might use it in order to prove quantitative statements about rates of convergence.

Feb 7th, 2019

Tsviqa Lakrec (HUJI)

Scenery Reconstruction for a Random Walk on Random Scenery with Adversarial Error Insertion

Consider a simple random walk on $\mathbb{Z}$ with a random coloring of $\mathbb{Z}$. Look at the sequence of the first $N$ steps taken and colors of the visited locations. From it, you can deduce the coloring of approximately $\sqrt{N}$ integers. Suppose an adversary may change $\delta N$ entries in that sequence. What can be deduced now? We show that for any $\theta<0.5,p>0$, there are $N_{0},\delta_{0}$ such that if $N>N_{0}$ and $\delta<\delta_{0}$ then with probability $>1-p$ we can reconstruct the coloring of $>N^{\theta}$ integers.

Jan 17th, 2019

Eliran Subag (Courant)

Optimization of random polynomials on the sphere in the full-RSB regime

To compute the spectral norm of a p-tensor one needs to optimize a homogeneous polynomial of degree p over the sphere. When p=2 (the matrix case) it is algorithmically easy, but for p>2 it can be NP-hard. In this talk I will focus on (randomized) optimization in high-dimensions when the objective function is a linear combination of homogeneous polynomials with Gaussian coefficients. Such random functions are called spherical spin glasses in physics and have been extensively studied since the 80s. I will describe certain geometric properties of spherical spin glasses unique to the full-RSB case, and explain how they can be used to design a polynomial time algorithm that finds points within a small multiplicative error from the global maximum.

Jan 24th, 2019

Noam Lifshitz (BIU)

Sharp thresholds for sparse functions with applications to extremal combinatorics.

The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy $\mu p(f)=o(\mu q(f))$, where $q = p + o(p)$, and $\mu p(f)$ is the probability that $f=1$ on an input with independent coordinates, each taking the value $1$ with probability $p$. The dense regime, where $\mu p(f)=\Theta(1)$, is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where $\mu p(f)=o(1)$ was out of reach of the available methods. However, the potential power of the sparse regime was envisioned by Kahn and Kalai already in 2006. In this talk we show that if a monotone Boolean function $f$ with $\mu p(f)=o(1)$ satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval $[p,q]$, with $q = p+o(p)$. More specifically, our mild pseudo-randomness hypothesis is that the $p$-biased measure of $f$ does not bump up to $\Theta(1)$ whenever we restrict $f$ to a sub-cube of constant co-dimension, and our conclusion is that we can find $q=p+o(p)$, such that $\mu p(f)=o(\mu q(f))$ At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influences'. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where $p = o(1)$. We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of Huang--Loh--Sudakov and Furedi--Jiang for a new wide range of the parameters. Based on a joint work with Keevash, Long, and Minzer.

Jan 10th, 2019

Godofredo Iommi (PUC Chile) + Paul Dario (ENS)

Godofredo Iommi: Upper semi-continuity of the entropy map for Markov shifts

In this talk I will show that for finite entropy countable Markov shifts the entropy map is upper semi-continuous when restricted to the set of ergodic measures. This is joint work with Mike Todd and Anibal Velozo.

Paul Dario: Homogenization on supercritical percolation cluster

The standard theory of stochastic homogenization requires an assumption of uniform ellipticity on the environment. In this talk, we investigate how one can remove this assumption in a specific case: the infinite cluster of the supercritical Bernouilli percolation of Zd. We will present a renormalization argument for the infinite cluster and show how one can use it to adapt the theory developped in the uniformly elliptic setting. We will then review some results which can be obtained through this technique: homogenization theorem, large scale regularity, Liouville theorem and bounds on the corrector.

Jan 3rd, 2019

Chaim Even-Zohar (UC Davis)

Patterns in Random Permutations

Every $k$ entries in a permutation can have one of k! different relative orders, called patterns. How many times does each pattern occur in a large random permutation of size $n$? The distribution of this k!-dimensional vector of pattern densities was studied by Janson, Nakamura, and Zeilberger (2015). Their analysis showed that some component of this vector is asymptotically multinormal of order $1/\sqrt(n)$, while the orthogonal component is smaller. Using representations of the symmetric group, and the theory of U-statistics, we refine the analysis of this distribution. We show that it decomposes into $k$ asymptotically uncorrelated components of different orders in $n$, that correspond to representations of $S_k$. Some combinations of pattern densities that arise in this decomposition have interpretations as practical nonparametric statistical tests.

Dec 20th, 2018

Max Fathi (Toulouse)

Stability in the Bakry-Emery theorem

The Bakry-Emery theorem asserts that uniformly log-concave probability measures satisfy certain functional inequalities, with constants that are better than those associated with the Gaussian measure. In this talk, I will explain how if the constant is almost that of the Gaussian, then the measure almost splits off a Gaussian factor, with explicit quantitative bounds. The proof is based on a combination of Stein's method and simple arguments from calculus of variations. Joint work with Thomas Courtade

Dec 27th, 2018

Yury Makarychev (TTIC)

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering

Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of $(1+\epsilon)$ under a projection onto a random $O(log(k/\epsilon)/\epsilon^2)$-dimensional subspace whp. Further, the cost of every clustering is preserved within $(1+\epsilon)$. Crucially, the dimension does not depend on the total number of points n in the instance. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant $p$. For k-means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan. Joint work with Konstantin Makarychev and Ilya Razenshteyn.

Dec 13th, 2018

Manuel Stadlbauer

Exponential decay of quotients of Ruelle operators

Ruelle’s operator theorem states that the Ruelle operator $L$, which is a positive operator acting on Holder functions, is conjugated to $P+R$ where $R$ is a one-dimensional projection and the norm of $R$ is smaller than 1. This decomposition, also known as spectral gap, is of interest as it allows to characterise the underlying dynamical system through, e.g., central limit theorems or continuous response to perturbations. However, the conjugation depends on the existence of a positive eigenfunction of $L$, which might not exist in more general, fibred situations due to purely functorial reasons. A possibility to circumvent this problem is to consider quotients of operators of the form $f \mapsto \frac{L^m(f L^n (1))}{L^{m+n}(1)}.$ In fact, it is possible to provide reasonable conditions such that their dual operators contract the Wasserstein distance exponentially in $m$. The result gives rise, for example, to a law of the iterated logarithm for continued fractions with sequentially restricted entries or a topology on the set of equilibrium states for semigroups of expanding maps. This is joint work with Paulo Varandas and Xuan Zhang.

Dec 6th, 2018

Boaz Slomka (WIS)

Improved bounds for Hadwiger’s covering problem via thin-shell estimates

A long-standing open problem, known as Hadwiger's covering problem, asks what is the smallest natural number $N(n)$ such that every convex body in {\mathbb R}^n can be covered by a union of the interiors of at most $N(n)$ of its translates. Despite continuous efforts, the best general upper bound known for this number remains as it was more than sixty years ago, of the order of ${2n \choose n} \ln n$. In this talk, I will discuss some history of this problem and present a new result in which we improve this bound by a sub-exponential factor. Our approach combines ideas from previous work, with tools from Asymptotic Geometric Analysis. As a key step, we use thin-shell estimates for isotropic log-concave measures to prove a new lower bound for the maximum volume of the intersection of a convex body $K$ with a translate of $-K$. We further show that the same bound holds for the volume of $K\cap(-K)$ if the center of mass of $K$ is at the origin. If time permits we shall discuss some other methods and results concerning this problem and its relatives. Joint work with H. Huang, B. Vritsiou, and T. Tkocz

Nov 29h, 2018

Amir Dembo (Stanford)

Large deviations of subgraph counts for sparse random graphs

For fixed t>1 and L>3 we establish sharp asymptotic formula for the log-probability that the number of cycles of length L in the Erdos - Renyi random graph G(N,p) exceeds its expectation by a factor t, assuming only that p >> log N/sqrt(N). We obtain such sharp upper tail bounds also for the Schatten norms of the corresponding adjacency matrices, and in a narrower range of p=p(N), also for general subgraph counts. In this talk, based on a recent joint work with Nick Cook, I will explain our approach and in particular our quantitative refinement of Szemeredi's regularity lemma for sparse random graphs in the large deviations regime.

Nov 8h, 2018

Snir Ben Ovadia (WIS)

What are SRB and GSRB measures, and a new characterisation of their existence

SRB measures are an important object in dynamical systems and mathematical physics. Named after Sinai , Ruelle and Bowen, these measures have important properties of being equilibrium states which describe chaotic behaviour, yet may also describe the asymptotic of ``observable” events in the phase space. An open and important question, is in what generality do systems admit SRB measures? We present the notion of generalised SRB measures (GSRB in short), mention some of their important properties, and present a new condition to characterise their existence on a general setup. The first part of the talk will describe some of the motivation leading to define and to study SRB measures; and so we will define GSRB measures and compare their properties with the properties sought for SRB measures. We will also describe a case study of examples motivating to study GSRB measures. Our new result is a characterisation of systems admitting GSRB measures. In the second part of the talk, as much as time permits, we will present some key steps in the construction of GSRB measures.

Oct 25th, 2018

Daniel Dadush (CWI Amsterdam)

Balancing vectors in any norm

In the vector balancing problem, we are given N vectors v_1,..., v_N in an n-dimensional normed space, and our goal is to assign signs to them, so that the norm of their signed sum is as small as possible. The balancing constant of the vectors is the smallest number beta, such that any subset of the vectors can be balanced so that their signed sum has norm at most beta. The vector balancing constant generalizes combinatorial discrepancy, and is related to rounding problems in combinatorial optimization, and to the approximate Caratheodory theorem. We study the question of efficiently approximating the vector balancing constant of any set of vectors, with respect to an arbitrary norm. We show that the vector balancing constant can be approximated in polynomial time to within factors logarithmic in the dimension, and is characterized by (an appropriately optimized version of) a known volumetric lower bound. Our techniques draw on results from geometric functional analysis and the theory of Gaussian processes. Our results also imply an improved approximation algorithm for hereditary discrepancy. Joint work with Aleksandar Nikolov, Nicole Tomczak-Jaegermann and Kunal Talwar.

Aug 30th, 2018

Assaf Naor (Princeton)

Coarse (non)Universality of Alexandrov Spaces

Aug 16th, 2018

David Ellis (Queen Mary U)

Random graphs with constant r-balls

Let $F$ be a fixed infinite, vertex-transitive graph. We say a graph $G$ is {\em $r$-locally $F$} if for every vertex $v$ of $G$, the ball of radius $r$ and centre $v$ in $G$ is isometric to the ball of radius $r$ in $F$. For each positive integer $n$, let $G_n$ be a graph chosen uniformly at random from the set of all unlabelled, $n$-vertex graphs that are $r$-locally $F$. We investigate the properties that the random graph $G_n$ has with high probability --- i.e., how these properties depend on the fixed graph $F$. We show that if $F$ is a Cayley graph of a torsion-free group of polynomial growth, then there exists a positive integer $r_0$ such that for every integer $r \geq r_0$, with high probability the random graph $G_n = G_n(F,r)$ defined above has largest component of size between $n^{c_1}$ and $n^{c_2}$, where $0 < c_1 < c_2 < 1$ are constants depending upon $F$ alone, and moreover that $G_n$ has a rather large automorphism group. This contrasts sharply with the random $d$-regular graph $G_n(d)$ (which corresponds to the case where $F$ is replaced by the infinite $d$-regular tree). Our proofs use a mixture of results and techniques from group theory, geometry and combinatorics. We obtain somewhat more precise results in the case where $F$ is $\mathbb{L}^d$ (the standard Cayley graph of $\mathbb{Z}^d$): for example, we obtain quite precise estimates on the number of $n$-vertex graphs that are $r$-locally $\mathbb{L}^d$, for $r$ at least linear in $d$. Many intriguing open problems remain: concerning groups with torsion, groups with faster than polynomial growth, and what happens for more general structures than graphs. This is joint work with Itai Benjamini (WIS).

July 26th, 2018

Eliran Subag (NYU)

Free energy landscapes in spherical spin glasses

I will describe a new approach to the study of spherical spin glass models via free energy landscapes, defined by associating to interior points of the sphere the free energy computed only over the spherical band around them. They are closely related to several fundamental objects from spin glass theory: the TAP free energy, pure states decomposition, overlap distribution, and temperature chaos. I will explain some of of those connections.

Jul 5th, 2018

Jonathan Hermon (Cambridge)

The exclusion process (usually) mixes faster than independent particles.

The exclusion process is one of the most basic and best studied processes in the literature on interacting particle systems, with connections to card shuffling and statistical mechanics. It has been one of the major examples driving the study of mixing-times. In the exclusion process on an n-vertex graph we have k black particles and n-k white particles, one per site. Each edge rings at rate 1. When an edge rings, the particles occupying its end-points switch positions. Oliveira conjectured that the order of the mixing time of the process is at most that of the mixing-time of k independent particles. Together with Richard Pymar we verify this up to a constant factor for d-regular (or bounded degree) graphs 1 in various cases: (1) the degree d is at least logarithmic in n, or (2) the spectral-gap of a single walk is small (at most log number of vertices to the power 4) or (3) when the number of particles k is roughly $n^a$ for some constant $a \in (0,1)$. In these cases our analysis yields a probabilistic proof of Aldous' famous spectral-gap conjecture (resolved by Caputo et al.). We also prove a general bound which (when $k \geq n^c$) is within a $\log \log n$ factor from Oliveira's conjecture. As applications we get new mixing bounds: (a) $O(\log n \log \log n)$ for expanders, (b) order $ \log (dk)$ for the hypercube ${0,1}^d$ and (c) order $(diameter)^2 \log k$ for vertex-transitive graphs of moderate growth and for the giant component of supercritical percolation on a torus.

June 28th, 2018

Omer Bobrowski (Technion)

Homological connectivity and percolation in random geometric complexes

Connectivity and percolation are two well studied phenomena in random graphs. In this talk we will discuss higher-dimensional analogues of connectivity and percolation that occur in random simplicial complexes. Simplicial complexes are a natural generalization of graphs, consisting of vertices, edges, triangles, tetrahedra, and higher dimensional simplexes. We will mainly focus on random geometric complexes. These complexes are generated by taking the vertices to be a random point process, and adding simplexes according to their geometric configuration. Our generalized notions of connectivity and percolation use the language of homology - an algebraic-topological structure representing cycles of different dimensions. In this talk we will review some recent progress in characterizing and analyzing these phenomena, as well as describing related phase transitions.

June 7th, 2018

Ohad Feldheim (HUJI) + Eviatar Procaccia (Texas A&M)

Ohad Feldheim: Convergence of a quantile admission processes.

Consider the following stochastic model for a growing set. At time $0$ the model consists of the singleton $S = \{-\infty\}$. At every subsequent time, two i.i.d. samples, distributed according to some distribution $D$ on $\mathbb{R}$, are suggested as candidates for $S$. If the smaller among the two is closer to at least a fraction of $r$ of the current elements of $S$ (in comparison with the larger one), then it is admitted into $S$. How will the distribution of the members of $S$ evolve over time as a function of $r$ and $D$? This model was suggested by Alon, Feldman, Mansour, Oren and Tennenholtz as a model for the evolution of an exclusive social group. We’ll show that the empirical distribution of the elements of $S$ converges to a (not-necessarily deterministic) limit distribution for any $r$ and $D$. This we do by relating the process to a random walk in changing environment. The analysis of this random walk involves various classical exponential concentration inequalities as well as a new general inequality concerning mean and minimum of independent random variables. Joint work with Naomi Feldheim.

Eviatar Procaccia: Stabilization of Diffusion Limited Aggregation in a Wedge.

We prove a discrete Beurling estimate for the harmonic measure in a wedge in $\mathbf{Z}^2$, and use it to show that Diffusion Limited Aggregation (DLA) in a wedge of angle smaller than $\pi/4$ stabilizes. This allows to consider the infinite DLA and questions about the number of arms, growth and dimension. I will present some conjectures and open problems.

June 14th, 2018

Emanuel Milman (Technion)

The Gaussian Double-Bubble and Multi-Bubble Conjectures

The classical Gaussian isoperimetric inequality, established in the 70’s independently by Sudakov-Tsirelson and Borell, states that the optimal way to decompose $\mathbb{R}^n$ into two sets of prescribed Gaussian measure, so that the (Gaussian) area of their interface is minimal, is by using two complementing half-planes. This is the Gaussian analogue of the classical Euclidean isoperimetric inequality, and is therefore referred to as the ``single-bubble” case. A natural generalization is to decompose $\mathbb{R}^n$ into $q \geq 3$ sets of prescribed Gaussian measure. It is conjectured that when $q \leq n+1$, the configuration whose interface has minimal (Gaussian) area is given by the Voronoi cells of $q$ equidistant points. For example, for $q=3$ (the ``double-bubble” conjecture) in the plane ($n=2$), the interface is conjectured to be a ``tripod” or ``Y” - three rays meeting at a single point in 120 degree angles. For $q=4$ (the ``triple-bubble” conjecture) in $\mathbb{R}^3$, the interface is conjectured to be a tetrahedral cone. We confirm the Gaussian double-bubble and, more generally, multi-bubble conjectures for all $3 \leq q \leq n+1$. The double-bubble case $q=3$ is simpler, and we will explain why. None of the numerous methods discovered over the years for establishing the classical $q=2$ case seem amenable to the $q \geq 3$ cases, and our method consists of establishing a Partial Differential Inequality satisfied by the isoperimetric profile. To treat $q > 3$, we first prove that locally minimimal configurations must have flat interfaces, and thus convex polyhedral cells. Uniqueness of minimizers up to null-sets is also established. This is joint work with Joe Neeman (UT Austin).

June 21st, 2018

No seminar (Conference at BIU)

May 31st, 2018

Bhaswar Bhattacharya (UPenn) + Elliot Paquette (Ohio)

Bhaswar Bhattacharya: Large Deviation Variational Problems in Random Combinatorial Structures

The upper tail problem in the Erdos-Renyi random graph $G\sim\mathcal{G}_{n,p}$, where every edge is included independently with probability $p$, is to estimate the probability that the number of copies of a graph $H$ in $G$ exceeds its expectation by a factor of $1+\delta$. The arithmetic analog of this problem counts the number of $k$-term arithmetic progressions in a random subset of $\{1, 2, \ldots, N\}$, where every element is included independently with probability $p$. The recently developed framework of non-linear large deviations (Chatterjee and Dembo (2016) and Eldan (2017)) shows that the logarithm of these tail probabilities can be reduced to a natural variational problem on the space of weighted graphs/functions. In this talk we will discuss methods for solving these variational problems in the sparse regime ($p \rightarrow 0$), and show how the solutions are often related to extremal problems in combinatorics. (This is based on joint work with Shirshendu Ganguly, Eyal Lubetzky, Xuancheng Shao, and Yufei Zhao.)

Elliot Paquette: Random matrix point processes via stochastic processes

In 2007, Virag and Valko introduced the Brownian carousel, a dynamical system that describes the eigenvalues of a canonical class of random matrices. This dynamical system can be reduced to a diffusion, the stochastic sine equation, a beautiful probabilistic object requiring no random matrix theory to understand. Many features of the limiting eigenvalue point process, the Sine--beta process, can then be studied via this stochastic process. We will sketch how this stochastic process is connected to eigenvalues of a random matrix and sketch an approach to two questions about the stochastic sine equation: deviations for the counting Sine--beta counting function and a functional central limit theorem.

May 24th, 2018

No seminar (IMU meeting in Technion)

TBA

May 17th, 2018

Ron Peled (TAU)

The fluctuations of random surfaces

Random surfaces in statistical physics are commonly modeled by a real-valued function phi on a lattice, whose probability density penalizes nearest-neighbor fluctuations. Precisely, given an even function $V$, termed the potential, the energy $H(\phi)$ is computed as the sum of $V$ over the nearest-neighbor gradients of phi, and the probability density of phi is set proportional to $\exp(-H(\phi))$. The most-studied case is when $V$ is quadratic, resulting in the so-called Gaussian free field. Brascamp, Lieb and Lebowitz initiated in 1975 the study of the global fluctuations of random surfaces for other potential functions and noted that understanding is lacking even in the case of the quartic potential, $V(x)=x^4$. We will review the state of the art for this problem and present recent work with Alexander Magazinov which finally settles the question of obtaining upper bounds for the fluctuations for the quartic and many other potential functions.

May 10th, 2018

David Jerison (MIT) + Ron Rosenthal (Technion)

David Jerison: Localization of eigenfunctions via an effective potential

We discuss joint work with Douglas Arnold, Guy David, Marcel Filoche and Svitlana Mayboroda. Consider the Neumann boundary value problem for the operator $L u = - \mbox{div} (A \nabla u) + Vu$ on a Lipschitz domain $\Omega$ and, more generally, on a manifold with or without boundary. The eigenfunctions of $L$ are often localized, as a result of disorder of the potential $V$, the matrix of coefficients $A$, irregularities of the boundary, or all of the above. In earlier work, Filoche and Mayboroda introduced the function $u$ solving $Lu = 1$, and showed numerically that it strongly reflects this localization. Here, we deepen the connection between the eigenfunctions and this {\em landscape} function $u$ by proving that its reciprocal $1/u$ acts as an {\em effective potential}. The effective potential governs the exponential decay of the eigenfunctions of the system and delivers information on the distribution of eigenvalues near the bottom of the spectrum.

Ron Rosenthal: Eigenvector correlation in the complex Ginibre ensemble

The complex Ginibre ensemble is a non-Hermitian random matrix on C^N with i.i.d. complex Gaussian entries normalized to have mean zero and variance 1=N. Unlike the Gaussian unitary ensemble, for which the eigenvectors are orthogonal, the geometry of the eigenbases of the Ginibre ensemble are not particularly well understood. We will discuss a some results regarding the analytic and algebraic structure of eigenvector correlations in this matrix ensemble. In particular, we uncover an extended algebraic structure which describes the asymptotic behavior (as N goes to infinity) of these correlations. Our work extends previous results of Chalker and Mehlig [CM98], in which the correlation for pairs of eigenvectors was computed. Based on a joint work with Nick Crawford.

April 26th, 2018

Anirban Basak (WIS)

Local weak limits of Ising and Potts measures on locally tree-like graphs.

Consider a sequence of growing graphs converging locally weakly to an infinite (possibly random) tree. As there are uncountably many Ising and Potts Gibbs measures on the limiting tree in the low-temperature regime it is not apriori clear whether the local weak limit of such measures exists and if so, identifying the limit remains a challenge. In this talk, I will describe these limits. The talk is based on joint works with Amir Dembo and Allan Sly.

April 12th, 2018

David Ellis (Queen Mary U) + Benjamin Fehrman (Max Planck Institute)

David Ellis - The edge-isoperimetric problem for antipodally symmetric subsets of the discrete cube.

A major open problem in geometry is to solve the isoperimetric problem for n-dimensional real projective space, i.e. to determine, for each real number V, the minimum possible size of the boundary of a (well-behaved) set of volume V, in n-dimensional real projective space. We study a discrete analogue of this question: namely, among all antipodally symmetric subsets of {0,1}^n of fixed size, which sets have minimal edge-boundary? We obtain a complete answer to the second question. This is joint work with Imre Leader (Cambridge)

Benjamin Fehrman - Well-posedness of stochastic porous media equations with nonlinear, conservative noise.

In this talk, which is based on joint work with Benjamin Gess, I will describe a pathwise well-posedness theory for stochastic porous media equations driven by nonlinear, conservative noise. Such equations arise in the theory of mean field games, as an approximation to the Dean-Kawasaki equation in fluctuating hydrodynamics, to describe the fluctuating hydrodynamics of a zero range process, and as a model for the evolution of a thin film in the regime of negligible surface tension. Our methods are loosely based on the theory of stochastic viscosity solutions, where the noise is removed by considering a class of test functions transported along underlying stochastic characteristics. We apply these ideas after passing to the equation's kinetic formulation, for which the noise enters linearly and can be inverted using the theory of rough paths.

March 22nd, 2018

Faculty retreat - no seminar

March 29th, 2018

Yinon Spinka (TAU) + Mark Rudelson (UMich)

Mark Rudelson: Invertibility of the adjacency matrices of random graphs.

Consider an adjacency matrix of a bipartite, directed, or undirected Erdos-Renyi random graph. If the average degree of a vertex is large enough, then such matrix is invertible with high probability. As the average degree decreases, the probability of the matrix being singular increases, and for a sufficiently small average degree, it becomes singular with probability close to 1. We will discuss when this transition occurs, and what the main reason for the singularity of the adjacency matrix is. This is a joint work with Anirban Basak.

Yinon Spinka: Finitary codings of Markov random fields

Let X be a stationary Z^d-process. We say that X can be coded by an i.i.d. process if there is a (deterministic and translation-invariant) way to construct a realization of X from i.i.d. variables associated to the sites of Z^d. That is, if there is an i.i.d. process Y and a measurable map F from the underlying space of Y to that of X, which commutes with translations of Z^d and satisfies that F(Y)=X in distribution. Such a coding is called finitary if, in order to determine the value of X at a given site, one only needs to look at a finite (but random) region of Y. It is known that a phase transition (existence of multiple Gibbs states) is an obstruction for the existence of such a finitary coding. On the other hand, we show that when X is a Markov random field satisfying certain spatial mixing conditions, then X can be coded by an i.i.d. process in a finitary manner. Moreover, the coding radius has exponential tails, so that typically the value of X at a given site is determined by a small region of Y. We give applications to models such as the Potts model, proper colorings and the hard-core model.

March 8th, 2018

Erwin Bolthausen (UZH)

On the high temperature phase in mean-field spin glasses

We present a new way to derive the replica symmetric solution for the free energy in mean-field spin glasses. Only the Sherrington-Kirpatrick case has been worked out in details, but the method also works in other cases, for instance for the perceptron (work in progress), and probably also for the Hopfield net. The method is closely related to the TAP equations (for Thouless-Anderson-Palmer). It does not give any new results, presently, but it gives a new viewpoint, and it looks to be quite promising. As the TAP equations are widely discussed in the physics literature, also at low temperature, it is hoped that the method could be extended to this case, too. But this is open, and probably very difficult.

March 15th, 2018

Elie Aidekon (Paris)

Points of infinite multiplicity of a planar Brownian motion.

Points of infinite multiplicity are particular points which the Brownian motion visits infinitely often. Following a work of Bass, Burdzy and Khoshnevisan, we construct and study a measure carried by these points. Joint work with Yueyun Hu and Zhan Shi.

Jan 18th, 2018

Oren Louidor (Technion) + Alexander Glazman (TAU)

Oren Louidor: Dynamical freezing in a spin-glass with logarithmic correlations.

We consider a continuous time random walk on the 2D torus, governed by the exponential of the discrete Gaussian free field acting as potential. This process can be viewed as Glauber dynamics for a spin-glass system with logarithmic correlations. Taking temperature to be below the freezing point, we then study this process both at pre-equilibrium and in-equilibrium time scales. In the former case, we show that the system exhibits aging and recover the arcsine law as asymptotics for a natural two point temporal correlation function. In the latter case, we show that the dynamics admits a functional scaling limit, with the limit given by a variant of Kolmogorov's K-process, driven by the limiting extremal process of the field, or alternatively, by a super-critical Liouville Brownian motion. Joint work with A. Cortines, J. Gold and A. Svejda.

Alexander Glazman: Level lines of a random Lipschitz function

We consider the uniform distribution on Lipschitz functions on the triangular lattice, i.e. all integer-valued functions which differ by 0 or 1 on any two adjacent vertices. We show that with a positive probability such a function exhibits macroscopic level lines. Instead of working directly with Lipschitz functions we map this model to the loop $O(2)$ model with parameter $x=1$. The loop $O(n)$ model is a model for a random collection of non-intersecting loops on the hexagonal lattice, which is believed to be in the same universality class as the spin $O(n)$ model. A main tool in the proof is a positive association (FKG) property that was recently shown to hold when $n \ge 1$ and $0

Jan 4th, 2018

Sebastien Bubeck (Microsoft) + Percy Deift (NYU)

Sebastien Bubeck: k-server via multiscale entropic regularization

I will start by describing how mirror descent is a natural strategy for online decision making, specifically in online learning and metrical task systems. To motivate the k-server problem I will also briefly recall what we know and what we don't know for structured state/action spaces in these models. Using the basic mirror descent calculations I will show how to easily obtain a log(k)-competitive algorithm for k-paging. I will then introduce our new parametrization of fractional k-server on a tree, and explain how to analyze the movement cost of entropy-regularized mirror descent on this parametrization. This leads to a depth*log(k)-competitive (fractional) algorithm for general trees, and log^2(k) for HSTs. I will also briefly mention dynamic embeddings to go beyond the standard log(n) loss in the reduction from general metrics to HSTs. Joint work with Michael B. Cohen, James R. Lee, Yin Tat Lee, and Aleksander Madry.

Percy Deift: Universality in numerical analysis with some examples of cryptographic algorithms.

We show that a wide variety of numerical algorithms with random data exhibit universality. Most of the results are computational, but in some important cases universality is established rigorously. We also discuss universality for some cryptographic algorithms. Joint work with C. Pfrany, G. Menon, S. Olver, T. Trogdan and S. Miller.

Dec 28th, 2017

Amir Dembo (Stanford) + Yuval Peres (Microsoft)

Amir Dembo: Large deviations theory for chemical reaction networks.

The microscopic dynamics of well-stirred networks of chemical reactions are modeled as jump Markov processes. At large volume, one may expect in this framework to have a straightforward application of large deviation theory. This is not at all true, for the jump rates are typically neither globally Lipschitz, nor bounded away from zero, with both blowup and absorption as quite possible scenarios. In joint work with Andrea Agazzi and Jean-Pierre Eckman, we utilize Lyapunov stability theory to bypass this challenge and to characterize a large class of network topologies that satisfy the full Wentzell-Freidlin theory of asymptotic rates of exit from domains of attraction.

Yuval Peres: Trace reconstruction for the deletion channel

In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability q, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability? The best lower bound known is linear in $n$. Until 2016, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some inequalities for Littlewood polynomials on the unit circle. This bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio). If the string $x$ is random, we can show a subpolynomial number of traces suffices by comparison to a random walk. (Joint works with Fedor Nazarov, STOC 2017, with Alex Zhai, FOCS 2017 and with Nina Holden & Robin Pemantle, preprint (2017).)

Dec 21st, 2017

Nadav Yesha (King's College London)

CLT for small scale mass distribution of toral Laplace eigenfunctions

In this talk we discuss the fine scale $L^2$-mass distribution of toral Laplace eigenfunctions with respect to random position. For the 2-dimensional torus, under certain flatness assumptions on the Fourier coefficients of the eigenfunctions and generic restrictions on energy levels, both the asymptotic shape of the variance and the limiting Gaussian law are established, in the optimal Planck-scale regime. We also discuss the 3-dimensional case, where the asymptotic behaviour of the variance is analysed in a more restrictive scenario. This is joint work with Igor Wigman.

Dec 7th, 2017

Matan Harel (TAU)

Discontinuity of the phase transition for the planar random-cluster and Potts models with $q > 4$

The random-cluster model is a dependent percolation model where the weight of a configuration is proportional to q to the power of the number of connected components. It is highly related to the ferromagnetic q-Potts model, where every vertex is assigned one of q colors, and monochromatic neighbors are encouraged. Through non-rigorous means, Baxter showed that the phase transition is first-order whenever $q > 4$ - i.e. there are multiple Gibbs measures at criticality. We provide a rigorous proof of this claim. Like Baxter, our proof uses the correspondence between the above models and the six-vertex model, which we analyze using the Bethe ansatz and transfer matrix techniques. We also prove Baxter's formula for the correlation length of the models at criticality. This is joint work with Hugo Duminil-Copin, Maxime Gangebin, Ioan Manolescu, and Vincent Tassion.

Nov 30th, 2017

Fanny Augeri (WIS)

Large deviations principles for random matrices

In this talk, I will try to present some techniques to handle the problem of large deviations of the spectrum of random matrices. I will focus on the case of macroscopic statistics of the spectrum of Hermitian matrices - in particular Wigner matrices - as the empirical distribution of the eigenvalues, the largest eigenvalue or the traces of powers. In a first part, I will be concerned with the so-called ``objective method''. Coined by David Aldous, this method consists in introducing, given a sequence of random objects, like random finite graphs, a new infinite random object from which one can deduce asymptotic properties of the original sequence. In the context of random matrices, this method has been mainly advertised by Balint Virag, and proven effective in showing universality results for the so-called beta-ensembles. Regarding large deviations of random matrices, this ``objective method'' amounts to embed our sequence of matrices with growing size into an appropriate space on which one is able to understand the large deviations, and carry out a contraction principle. I will review several large deviations principles obtained by this method, given by interpretations of random matrices as either dense or sparse graphs, and point out the limits of this strategy. In a second part, I will present a different approach which is inspired from Ledoux's proof of the large deviations of Wiener chaoses. I will give a large deviations principles for the traces of Gaussian Wigner matrices using this strategy. Similarly as for Wiener chaoses, where the deviations are obtained by translations in the direction of the reproducing kernel, the large deviations of the traces of Gaussian Wigner matrices are due to additive perturbations of the underlying matrix. If time permits, I will explain how this approach can be generalized to large deviations governed by the same phenomenon. In particular, this approach enables us to partially recover some large deviations results for a family of Wigner matrices which exhibit a ``heavy-tail phenomenon'', meaning that the deviations of their spectrum are due to the deviations of a negligible proportion of the entries.

Nov 23rd, 2017

Naomi Feldheim (WIS)

Persistence of Gaussian Stationary Processes

Nov 9th, 2017

Ilya Goldsheid (Queen Many University)

Real and complex eigenvalues of the non-self-adjoint Anderson model

June 29th, 2017

Amir Dembo (Stanford)

The criticality of a randomly-driven front

Consider independent continuous-time random walks on the integers to the right of a front R(t). Starting at R(0)=0, whenever a particle attempts to jump into the front, the latter instantaneously advances k steps to the right, absorbing all particles along its path. Sly (2016) resolves the question of Kesten and Sidoravicius (2008), by showing that for k=1 the front R(t) advances linearly once the particle density exceeds 1, but little is known about the large t asymptotic of R(t) at critical density 1. In a joint work with L-C Tsai, for the variant model with k taken as the minimal random integer such that exactly k particles are absorbed by the move of R(t), we obtain both scaling exponent and the random scaling limit for the front at the critical density 1. Our result unveils a rarely seen phenomenon where the macroscopic scaling exponent is sensitive to the initial local fluctuations (with the scaling limit oscillating between instantaneous super and sub-critical phases).

June 15th, 2017

Pyotr Nayar (Technion)

Gaussian mixtures with applications to entropy inequalities and convex geometry

We say that a symmetric random variable X is a Gaussian mixture if X has the same distribution as YG, where G is a standard Gaussian random variable, and Y is a positive random variable independent of G. In the first part of the talk we use this simple notion to study the Shannon entropy of sums of independent random variables. In the second part we investigate, using Gaussian mixtures, certain topics related to the geometry of $B_p^n$ balls, including optimal Khinchine-type inequalities and Schur-type comparison for volumes of section and projections of these sets. In the third part we discuss extensions of Gaussian correlation inequality to the case of p-stable laws and uniform measure on the Euclidean sphere. Based on a joint work with Alexandros Eskenazis and Tomasz Tkocz.

June 8th, 2017

Nishant Chandgotia (Tel Aviv University)

Irrational rotations, random affine transformations and the central limit theorem

It is a well-known result from Hermann Weyl that if alpha is an irrational number in [0,1) then the number of visits of successive multiples of alpha modulo one in an interval contained in [0,1) is proportional to the size of the interval. In this talk we will revisit this problem, now looking at finer joint asymptotics of visits to several intervals with rational end points. We observe that the visit distribution can be modelled using random affine transformations; in the case when the irrational is quadratic we obtain a central limit theorem as well. Not much background in probability will be assumed. This is in joint work with Jon Aaronson and Michael Bromberg.

March 9th, 2017

Sasha Shamov

Conditional determinantal processes are determinantal

A determinantal point process governed by a locally trace class Hermitian contraction kernel on a measure space $E$ remains determinantal when conditioned on its configuration on an arbitrary measurable subset $B \subset E$. Moreover, the conditional kernel can be chosen canonically in a way that is "local" in a non-commutative sense, i.e. invariant under "restriction" to closed subspaces $L^2(B) \subset P \subset L^2(E)$. Using the properties of the canonical conditional kernel we establish a conjecture of Lyons and Peres: if $K$ is a projection then almost surely all functions in its image can be recovered by sampling at the points of the process.

Feb 9th, 2017

Alexander Fish (Sydney)

The values of quadratic forms on difference sets, measure rigidity and equidistribution.

Given a quadratic form Q in d variables over the integers, e.g. Q(x,y,z) = xy - z^2, and a set of positive density E in Z^d, we investigate what kind of structure can be found in the set Q(E-E). We will see that if d >= 3, and Q is indefinite, then the measure rigidity, due to Bourgain-Furman-Lindenstrauss-Mozes or Benoist-Quint, of the action of the group of the symmetries of Q implies that there exists k >=1 such that k^2*Q(Z^d) is a subset of Q(E-E). We will give an alternative proof of the theorem for the case Q(x,y,z) = xy - z^2 that uses more classical equidistribution results of Vinogradov, and Weyl, as well as a more recent result by Frantzikinakis-Kra. The latter proof extends the theorem to other polynomials having a much smaller group of symmetries. Based on joint works with M. Bjorklund (Chalmers), and K. Bulinski (Sydney).

Jan 19th, 2017

Jay Rosen

Tightness for the Cover Time of $S^{2}$

Let M be a smooth, compact, connected two-dimensional, Riemannian manifold without boundary, and let $ C_{\epsilon}$ be the amount of time needed for the Brownian motion to come within (Riemannian) distance $\epsilon$ of all points in M. The first order asymptotics of $ C_{\epsilon}$ as $\epsilon$ goes to 0 are known. We show that for the two dimensional sphere $\sqrt{C_{\epsilon}}-2\sqrt{2}\left( \log \epsilon^{-1}- \frac{1}{4}\log\log \epsilon^{-1}\right)$is tight. Joint work with David Belius and Ofer Zeitouni.

Jan 12th, 2017

Ran Tessler (ETH) + Assaf Naor (Princeton)

Ran Tessler (11:00): A sharp threshold for Hamiltonian spheres in a random 2-complex

We define the notion of Hamiltonian sphere - a 2-complex homeomorphic to a sphere which uses all vertices. We prove an explicit sharp threshold for the appearance of Hamiltonian spheres in the Linial-Meshulam model for random 2-complexes. The proof combines combinatorial, probabilistic and geometric arguments. Based on a joint work with Zur luria.

Assaf Naor (12:00): A new vertical-versus-horizontal isoperimetric inequality on the Heisenberg group, with applications to metric geometry and approximation algorithms.

In this talk we will show that for every measurable subset of the Heisenberg group of dimension at least 5, an appropriately defined notion of its "vertical perimeter" is at most a constant multiple of its horizontal (Heisenberg) perimeter. We will explain how this new isoperimetric-type inequality solves open questions in analysis (an endpoint estimate for a certain singular integral on $W^{1,1}$), metric geometry (sharp nonembeddability into $L_1$) and approximation algorithms (asymptotic evaluation of the performance of the Goemans-Linial algorithm for the Sparsest Cut problem). Joint work with Robert Young.

Jan 5th, 2017

Amir Dembo

Title: Walking within growing domains: recurrence versus transience

When is simple random walk on growing in time d-dimensional domains recurrent? For domain growth which is independent of the walk, we review recent progress and related universality conjectures about a sharp recurrence versus transience criterion in terms of the growth rate. We compare this with the question of recurrence/transience for time varying conductance models, where Gaussian heat kernel estimates and evolving sets play an important role. We also briefly contrast such expected universality with examples of the rich behavior encountered when monotone interaction enforces the growth as a result of visits by the walk to the current domain's boundary. This talk is based on joint works with Ruojun Huang, Ben Morris, Yuval Peres, Vladas Sidoravicius and Tianyi Zheng.

For previous years see: 2010-2016, 2007-2010, 2005-2007 (maintained by Boaz Tsaban) 2000-2005 (maintained by Gideon Schechtman)