Geometric Functional Analysis and Probability Seminar

Szekeres proved in 1982 that the diameter (length of longest path) of a uniformly drawn labeled tree on n vertices normalized by the square root of n converges in distribution to an explicitly described distribution. This random tree is just a uniformly chosen spanning tree of the complete graph on n vertices. What if one changes the underlying graph from the complete graph to, say, the hypercube {0,1}^n, or an expander graph, or in cubic lattices of fixed but high dimensions? Our result shows that one gets the same limiting distribution of the diameter. In fact much more is true: any reasonable "global" property of these random trees will have the same limiting distribution as a uniformly chosen labelled tree, moreover, these distributions can be explicitly described via Aldous' 1991 continuum random tree.

Joint work with Eleanor Archer and Matan Shalev.

A paper of Benaim, Benjamini, Chen and Lima introduced a model of Polya urns with graph-based interactions. For these systems, the proportions of balls in the bins converge almost surely. In this talk, I will discuss the hypergraph-based version of this model, and report on partial results about the convergence of the proportions of balls in the bins, in terms of the incidence matrix of the hypergraph.

Consider a system of Brownian particles on the real line where each pair of particles coalesces at a certain rate according to their intersection local time.

Assume that initially there are infinitely many particles in the system. We give conditions for the number of particles to come down from infinity.

We also identify the rate of the coming down from infinity for different initial configurations.

This is a joint work with C. Barnes and Z. Sun.

Log-correlated Gaussian fields are a class of random interface models which show a very rich behaviour. In the last decade there has been great progress in the understanding of the extrema of these fields, and it has been shown for various examples that the recentred maximum of the field converges in distribution.
In this talk I will briefly summarize these results, and then explain how to extend them to some fields in an environment which is itself random. In particular, I will discuss the example of the Gaussian free field on the two-dimensional supercritical percolation cluster. This requires sharp quenched estimates on the Green’s function of the Laplacian on the cluster.

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.

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.

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.  

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.

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,∞) 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.

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.)

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.  

There 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).

Speaker 1: Mark Rudelson (UMich)

Title: Circular law for sparse random matrices.

Abstract: 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.

Speaker 2: Serguei Popov (IMECC)

Title: On the range of a two-dimensional conditioned random walk

Abstract: 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!

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.

 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)

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.

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 Erdos 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).

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.

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.

Godofredo Iommi (PUC Chile)

Title: Upper semi-continuity of the entropy map for Markov shifts
Abstract: 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 (ENS)

Title: Homogenization on supercritical percolation cluster
Abstract: 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.

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.

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.

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.

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.

Let F be a fixed infinite, vertex-transitive graph. We say a graph G is `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 at least 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 L^d (the standard Cayley graph of Z^d): for example, we obtain quite precise estimates on the number of n-vertex graphs that are r-locally 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).

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).

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.

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.

Talk 1: David Ellis (Queen Mary U)
Title: The edge-isoperimetric problem for antipodally symmetric subsets of the discrete cube.
Abstract: 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)

Talk 2:  Benjamin Fehrman (Max Planck Institute)
Title: Well-posedness of stochastic porous media equations with nonlinear, conservative noise.
Abstract: 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.

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.

Oren Louidor (Technion)
Title: Dynamical freezing in a spin-glass with logarithmic correlations.
Abstract: 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 (Tel Aviv)
Title: Level lines of a random Lipschitz function
Abstract: 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<x\le\frac{1}{\sqrt{n}}$. Though the case $n=2$, $x=1$ is not in the FKG regime, it turns out that when loops are assigned one of two colours independently the marginal on loops of either of the colours does satisfy the FKG property. The colouring of loops allows to view the loop $O(2)$ model with $x=1$ as coupling of two percolation configurations. Studying each of them independently and using the XOR operation we establish existence of macroscopic loops, i.e. level lines in the original setting.
(Based on a joint work with H. Duminil-Copin, and I. Manolescu)

Talk 1: Amir Dembo (Stanford) 

Title: 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.

Talk 2: Yuval Peres (Microsoft)
Title: Trace reconstruction for the deletion channel
Abstract: 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).)

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.

Consider a real Gaussian stationary process, either on Z or on R.
What is the probability that it remains positive on [0,N] for large N?

The relation between this probability, known as the persistence probability, and the covariance kernel of the process has been investigated since the 1950s with motivations stemming from probability, engineering and mathematical physics. Nonetheless, until recently, good estimates were known only for particular cases, or when the covariance kernel is either non-negative or summable.

In the first hour of the talk we will discuss new spectral methods which greatly simplify the analysis of persistence. We will then describe its qualitative behavior in a very general setting.

In the second hour, we will describe (very) recent progress. In particular we will show the proof of the "spectral gap conjecture'', which states: if the spectral measure vanishes on an interval containing 0 then the persistence is less then e^{-cN^2}, and this bound is tight if the measure is non-singular and compactly supported. 
Time permitting, we will also discuss "tiny persistence'' phenomena (of the order of e^{-e^{cN}}).

Based on joint works with Ohad Feldheim, Benjamin Jaye, Fedor Nazarov and Shahaf Nitzan.

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). 

First Speaker: Ran Tessler (ETH)
Time: 11:00
Title: A sharp threshold for Hamiltonian spheres in a random 2-complex.
Abstract: 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.

Second Speaker: Assaf Naor (Princeton)
Time: 12:00
Title: A new vertical-versus-horizontal isoperimetric inequality on the Heisenberg group, with applications to metric geometry and approximation algorithms
Abstract: 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.

Consider the Gaussian Entire Function (GEF) whose Taylor coefficients are independent complex-valued Gaussian variables, and the variance of the k-th coefficient is 1/k!. This random Taylor series is distinguished by the invariance of its zero set with respect to the isometries of the complex plane.
I will show that the law of the zero set, conditioned on the GEF having no zeros in a disk of radius r, and properly normalized, converges to an explicit limiting Radon measure in the plane, as r goes to infinity. A remarkable feature of this limiting measure is the existence of a large 'forbidden region' between a singular part supported on the boundary of the (scaled) hole and the equilibrium measure far from the hole. This answers a question posed by Nazarov and Sodin, and is in stark contrast to the corresponding result known to hold in the random matrix setting, where such a gap does not appear.
The talk is based on a joint work with S. Ghosh.

There are numerous essentially equivalent characterizations of mixing in $L_1$ of a finite Markov chain. Some of these characterizations involve natural probabilistic concepts such as couplings, stopping times and hitting times. In contrast, while there are several analytic and geometric tools for bounding the $L_2$ mixing time, none of them are tight and they do not have a probabilistic interpretation.

We provide tight probabilistic characterizations in terms of hitting times distributions for mixing in $L_2$ (for normal chains) and (under reversibility) in relative entropy. This is done by assigning appropriate penalty (depending on the size of the set) to the case that the chain did not escape from a certain set.

We also prove a new extremal characterization of the log-sobolev constant in terms of a weighted version of the spectral gap (where the weight depends on the size of the support of the function).

Projection inequalities bound the volume of a body in terms of a product of the volumes of lower-dimensional projections of the body. Two well-known examples are the Loomis-Whitney inequality and the more general Uniform Cover inequality. We will see how to use information theory to prove stability versions of these inequalities, showing that when they are close to being tight, the body in question is close to being a box (which is the unique case of equality). We will also see how to obtain a stability result for the edge-isoperimetric inequality in the infinite d-dimensional lattice. Namely, that a subset of Z^d with small edge-boundary must be close in symmetric difference to a d-dimensional cube.

Based on work with David Ellis, Ehud Friedgut and Guy Kindler.

Heuristically, delocalization for a random matrix means that its normalized eigenvectors look like the vectors uniformly distributed over the unit sphere. This can be made precise in a number of different ways. We show that with high probability, any sufficiently large set of coordinates of an eigenvector carries a non-negligible portion of its Euclidean norm. Our results pertain to a large class of random matrices including matrices with independent entries, symmetric, skew-symmetric matrices, as well as more general ensembles.

Joint work with Roman Vershynin.

Erdös-Ko-Rado (EKR) type theorems yield upper bounds on the size of set families under various intersection requirements on the elements. Stability versions of such theorems assert that if the size of a family is close to the maximum possible then the family itself must be close (in appropriate sense) to a maximum family. In this talk we present an approach to stability versions of EKR-type theorems through isoperimetric inequalities for subsets of the hypercube. We use this approach to obtain tight stability versions of the EKR theorem itself and of the Ahlswede-Khachatrian theorem on t-intersecting families (for k < n/(t+1)), and to show that, somewhat surprisingly, both theorems hold when the "intersection" requirement is replaced by a much weaker requirement. Furthermore, we obtain stability versions of several recent EKR-type results, including Frankl's proof of the Erdös matching conjecture for n>(2s+1)k-s.

Joint work with David Ellis and Noam Lifshitz.

Recently, the "information percolation" framework was introduced as a way to obtain sharp estimates on mixing for spin systems at high temperatures, and in particular, to establish cutoff for the Ising model in three dimensions up to criticality from a worst starting state. I will describe how this method can be used to understand the effect of different initial states on the mixing time, both random (''warm start'') and deterministic.

Joint work with Allan Sly.

The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of M=Nd/2 edges, the leading correction to M/2 (the typical cut size), is P∗sqrt(NM/2). Here P∗ is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula.

This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.

We consider two stationary versions of the Eden model, on the upper half planar lattice, resulting in an infinite forest covering the half plane. Under weak assumptions on the weight distribution and by relying on ergodic theorems, we prove that almost surely all trees are finite. Using the mass transport principle, we generalize the result to Eden model in graphs of the form $G \times Z$, where G is a Cayley graph. This generalizes certain known results on the two-type Richardson model, in particular of Deijfen and Häggström in 2007.

Consider a random coloring of a bounded domain in Z^d with the probability of each coloring F proportional to exp(−β∗N(F)), where β>0 is a parameter (representing the inverse temperature) and N(F) is the number of nearest neighboring pairs colored by the same color. This is the anti-ferromagnetic 3-state Potts model of statistical physics, used to describe magnetic interactions in a spin system. The Kotecký conjecture is that in such a model, for d≥3 and high enough β, a sampled coloring will typically exhibit long-range order, placing the same color at most of either the even or odd vertices of the domain. We give the first rigorous proof of this fact for large d. This extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the case β=∞.

The main ingredient in our proof is a new structure theorem for 3-colorings which characterizes the ways in which different "phases" may interact, putting special emphasis on the role of edges connecting vertices of the same color. We also discuss several related conjectures. No background in statistical physics will be assumed and all terms will be explained thoroughly.

Joint work with Ohad Feldheim.

Consider a random finite metric space X given by sampling n points in the unit interval uniformly, and a deterministic finite metric space U given by placing n points in the unit interval at uniform distance. With high probability, X will contain some pairs of points at distance roughly 1/n^2, so any bijection from X to U must distort distances by a factor of roughly n. However, with high probability, two of these random spaces, X_1 and X_2, have a bijection which distorts distances by a factor of only about n^2/3. The exponent of 2/3 is optimal.

Branching processes have been subject of intense and fascinating studies for a long time. In my talk I will present two problems in order to highlight their rich structure and various technical approaches in the intersection of probability and analysis.
Firstly, I will present results concerning a branching random walk with the time-inhomogeneous branching law. We consider a system of particles, which at the end of each time unit produce offspring randomly and independently. The branching law, determining the number and locations of the offspring is the same for all particles in a given generation. Until recently, a common assumption was that the branching law does not change over time. In a pioneering work, Fang and Zeitouni (2010) considered a process with two macroscopic time intervals with different branching laws. In my talk I will present the results when the branching law varies at mesoscopic and microscopic scales. In arguably the most interesting case, when the branching law is sampled randomly for every step, I will present a quenched result with detailed asymptotics of the maximal particle. Interestingly, the disorder has a slowing-down effect manifesting itself on the log level.
Secondly, I will turn to the classical branching Brownian motion. Let us assume that particles move according to a Brownian motion with drift μ and split with intensity 1. It is well-know that for μ≥2√ the system escapes to infinity, thus the overall minimum is well-defined. In order to understand it better, we modify the process such that the particles are absorbed at position 0. I will present the results concerning the law of the number of absorbed particles N. In particular I will concentrate on P(N=0) and the maximal exponential moment of N. This reveals new deep connections with the FKPP equation. Finally, I will also consider −2√<μ<2√ and Nxt the number of particles absorbed until the time t when the system starts from x. In this case I will show the convergence to the traveling wave solution of the FKPP equation for an appropriate choice of x,t−>∞.
The results were obtained jointly with B. Mallein and with J. Berestycki, E. Brunet and S. Harris respectively.

Examine random walk in a stationary, ergodic, random environment which is bistochastic i.e. the sum of probabilities to enter any fixed vertex is 1. Consider the drift as a function on the probability space on the environments, and assume it belongs to domain of definition of where D is the symmetrized generator of the walk (this is the famous   condition). We show that under these conditions the walk satisfies a central limit theorem. The proof uses the "relaxed sector condition" which shows an unexpected connection to the spectral theory of unbounded operators.

All terms will be explained in the talk. This is joint work with Balint Toth.