Ofer Zeitouni

Lower Bounds on the Generalization Error of Nonlinear Learning Models

We study in this paper lower bounds for the generalization error of models derived from multi-layer neural networks, in the regime where the size of the layers is commensurate with the number of samples in the training data. We show that unbiased estimators have unacceptable performance for such nonlinear networks in this regime. We derive explicit generalization lower bounds for general biased estimators, in the cases of linear regression and of two-layered networks. In the linear case the bound is asymptotically tight. In the nonlinear case, we provide a comparison of our bounds with an empirical study of the stochastic gradient descent algorithm. The analysis uses elements from the theory of large random matrices.

On the limiting law of line ensembles of Brownian polymers with geometric area tilts

We study the line ensembles of non-crossing Brownian bridges above a hard wall, each tilted by the area of the region below it with geometrically growing pre-factors. This model, which mimics the level lines of the $(2+1)$ D SOS model above a hard wall, was studied in two works from 2019 by Caputo, Ioffe and Wachtel. In those works, the tightness of the law of the top $k$ paths, for any fixed $k$ , was established under either zero or free boundary conditions, which in the former setting implied the existence of a limit via a monotonicity argument. Here we address the open problem of a limit under free boundary conditions: we prove that as the interval length, followed by the number of paths, go to $\infty$ , the top $k$ paths converge to the same limit as in the free boundary case, as conjectured by Caputo, Ioffe and Wachtel.

The maximum of branching Brownian motion in $\mathbb{R}^d$

We show that in branching Brownian motion (BBM) in $\mathbb{R}^d$ , $d\geq 2$ , the law of $R_t^*$ , the maximum distance of a particle from the origin at time $t$ , converges as $t\to\infty$ to the law of a randomly shifted Gumbel random variable.

The maximum of log-correlated Gaussian fields in random environments

We study the distribution of the maximum of a large class of Gaussian fields indexed by a box $V_N\subset Z^d$ and possessing logarithmic correlations up to local defects that are sufficiently rare. Under appropriate assumptions that generalize those in Ding, Roy and Zeitouni (Annals Probab. (45) 2017, 3886-3928), we show that asymptotically, the centered maximum of the field has a randomly-shifted Gumbel distribution. We prove that the two dimensional Gaussian free field on a super-critical bond percolation cluster with $p$ close enough to $1$ , as well as the Gaussian free field in i.i.d. bounded conductances, fall under the assumptions of our general theorem.

Universality of Poisson limits for moduli of roots of Kac polynomials

We give a new proof of a recent resolution by Michelen and Sahasrabudhe of a conjecture of Shepp and Vanderbei that the moduli of roots of Gaussian Kac polynomials of degree $n$ , centered at $1$ and rescaled by $n^2$ , should form a Poisson point process. We use this new approach to verify a conjecture of Michelen and Sahasrabudhe that the Poisson statistics are in fact universal.

Deterministic equivalence for noisy perturbations

We prove a quantitative deterministic equivalence theorem for the logarithmic potentials of deterministic complex $N\times N$ matrices subject to small random perturbations. We show that with probability close to $1$ this log-potential is, up to a small error, determined by the singular values of the unperturbed matrix which are larger than some small $N$ -dependent cut-off parameter.

Everything is a Race and Nakamoto Always Wins

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

Maximum of Branching Brownian motion in a periodic environment

We study the maximum of Branching Brownian motion (BBM) with branching rates that vary in space, via a periodic function of a particle's location. This corresponds to a variant of the F-KPP equation in a periodic medium, extensively studied in the last 15 years, admitting pulsating fronts as solutions. Recent progress on this PDE due to Hamel, Nolen, Roquejoffre and Ryzhik ('16) implies tightness for the centered maximum of BBM in a periodic environment. Here we establish the convergence in distribution of specific subsequences of this centered maximum, and identify the limiting distribution. Consequently, we find the asymptotic shift between the solution to the corresponding F-KPP equation with Heavyside initial data and the pulsating wave, thereby answering a question of Hamel et al. Analogous results are given for the cases where the Brownian motion is replaced by an Ito diffusion with periodic coefficients, as well as for nearest-neighbor branching random walks.

Outliers of random perturbations of Toeplitz matrices with finite symbols

Consider an $N\times N$ Toeplitz matrix $T_N$ with symbol ${a }(λ) := \sum_{\ell=-d_2}^{d_1} a_\ell λ^\ell$ , perturbed by an additive noise matrix $N^{-γ} E_N$ , where the entries of $E_N$ are centered i.i.d.~random variables of unit variance and $γ>1/2$ . It is known that the empirical measure of eigenvalues of the perturbed matrix converges weakly, as $N\to\infty$ , to the law of ${a}(U)$ , where $U$ is distributed uniformly on $\mathbb{S}^1$ . In this paper, we consider the outliers, i.e. eigenvalues that are at a positive ( $N$ -independent) distance from ${a}(\mathbb{S}^1)$ . We prove that there are no outliers outside ${\rm spec} \, T({a})$ , the spectrum of the limiting Toeplitz operator, with probability approaching one, as $N \to \infty$ . {In contrast,} in ${\rm spec}\, T({a})\setminus {a}({\mathbb S}^1)$ the process of outliers converges to the point process described by the zero set of certain random {analytic} functions. The limiting random {analytic} functions can be expressed as linear combinations of the determinants of finite sub-matrices of an infinite dimensional matrix, whose entries are i.i.d.~having the same law as that of $E_N$ . The coefficients in the linear combination depend on the roots of the polynomial $P_{z, {a}}(λ):= ({a}(λ) -z)λ^{d_2}=0$ and semi-standard Young Tableaux with shapes determined by the number of roots of $P_{z,{a}}(λ)=0$ that are greater than one in moduli.

Proof-of-Stake Longest Chain Protocols: Security vs Predictability

The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamoto's longest chain design achieve provable security only by allowing long-term predictability (which have serious security implications). In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto's PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols that achieve security against a 50% adversary, while only requiring short-term predictability. Our proofs present a new approach to analyzing the formal security of blockchains, based on a notion of adversary-proof convergence.

The Erdős-Rényi law of large numbers for ballistic random walk in random environment

We consider a one dimensional ballistic nearest-neighbor random walk in a random environment. We prove an Erdős-Rényi strong law for the increments.

Tightness for the Cover Time of the two dimensional sphere

Let $C^*_{ε,S^2}$ denote the cover time of the two dimensional sphere by a Wiener sausage of radius $ε$ . We prove that $\sqrt{C^{*}_{ε,S^2} } -\sqrt{\frac{2A_{S^2}}π}(\log ε^{-1}-\frac14\log\log ε^{-1})$ is tight, where $A_{S^2}=4π$ denotes the Riemannian area of $S^2$ .

Universality for Langevin-like spin glass dynamics

We study dynamics for asymmetric spin glass models, proposed by Hertz et al. and Sompolinsky et al. in the 1980's in the context of neural networks: particles evolve via a modified Langevin dynamics for the Sherrington--Kirkpatrick model with soft spins, whereby the disorder is i.i.d. standard Gaussian rather than symmetric. Ben Arous and Guionnet (1995), followed by Guionnet (1997), proved for Gaussian interactions that as the number of particles grows, the short-term empirical law of this dynamics converges a.s. to a non-random law $μ_\star$ of a ``self-consistent single spin dynamics,'' as predicted by physicists. Here we obtain universality of this fact: For asymmetric disorder given by i.i.d. variables of zero mean, unit variance and exponential or better tail decay, at every temperature, the empirical law of sample paths of the Langevin-like dynamics in a fixed time interval has the same a.s. limit $μ_\star$ .

preprint2017arXiv

Homogenization of a class of one-dimensional nonconvex viscous Hamilton-Jacobi equations with random potential

We prove the homogenization of a class of one-dimensional viscous Hamilton-Jacobi equations with random Hamiltonians that are nonconvex in the gradient variable. Due to the special form of the Hamiltonians, the solutions of these PDEs with linear initial conditions have representations involving exponential expectations of controlled Brownian motion in a random potential. The effective Hamiltonian is the asymptotic rate of growth of these exponential expectations as time goes to infinity and is explicit in terms of the tilted free energy of (uncontrolled) Brownian motion in a random potential. The proof involves large deviations, construction of correctors which lead to exponential martingales, and identification of asymptotically optimal policies.

Convergence in law of the maximum of nonlattice branching random walk

Let $η^*_n$ denote the maximum, at time $n$ , of a nonlattice one-dimensional branching random walk $η_n$ possessing (enough) exponential moments. In a seminal paper, Aidekon demonstrated convergence of $η^*_n$ in law, after recentering, and gave a representation of the limit. We give here a shorter proof of this convergence by employing reasoning motivated by Bramson, Ding and Zeitouni. Instead of spine methods and a careful analysis of the renewal measure for killed random walks, our approach employs a modified version of the second moment method that may be of independent interest.

Hafnians, perfect matchings and Gaussian matrices

We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with nonnegative entries. We introduce a condition under which the Barvinok estimator achieves subexponential errors, and show that this condition is almost optimal. Using that hafnians count the number of perfect matchings in graphs, we conclude that Barvinok's estimator gives a polynomial-time algorithm for the approximate (up to subexponential errors) evaluation of the number of perfect matchings.

Large Deviations and Sum Rules for Spectral Theory - A Pedagogical Approach

This is a pedagogical exposition of the large deviation approach to sum rules pioneered by Gamboa, Nagel and Rouault. We'll explain how to use their ideas to recover the Szeg}o and Killip{ Simon Theorems. The primary audience is spectral theorists and people working on orthogonal polynomials who have limited familiarity with the theory of large deviations.

Local asymptotics for controlled martingales

We consider controlled martingales with bounded steps where the controller is allowed at each step to choose the distribution of the next step, and where the goal is to hit a fixed ball at the origin at time $n$ . We show that the algebraic rate of decay (as $n$ increases to infinity) of the value function in the discrete setup coincides with its continuous counterpart, provided a reachability assumption is satisfied. We also study in some detail the uniformly elliptic case and obtain explicit bounds on the rate of decay. This generalizes and improves upon several recent studies of the one dimensional case, and is a discrete analogue of a stochastic control problem recently investigated in Armstrong and Trokhimtchouck [Calc. Var. Partial Differential Equations 38 (2010) 521-540].

The extremal process of critical points of the pure $p$ -spin spherical spin glass model

Recently, sharp results concerning the critical points of the Hamiltonian of the $p$ -spin spherical spin glass model have been obtained by means of moments computations. In particular, these moments computations allow for the evaluation of the leading term of the ground-state, i.e., of the global minimum. In this paper, we study the extremal point process of critical points - that is, the point process associated to all critical values in the vicinity of the ground-state. We show that the latter converges in distribution to a Poisson point process of exponential intensity. In particular, we identify the correct centering of the ground-state and prove the convergence in distribution of the centered minimum to a (minus) Gumbel variable. These results are identical to what one obtains for a sequence of i.i.d variables, correctly normalized; namely, we show that the model is in the universality class of REM.

Universal large deviations for Kac polynomials

We prove the universality of the large deviations principle for the empirical measures of zeros of random polynomials whose coefficients are i.i.d. random variables possessing a density with respect to the Lebesgue measure on C, R or R + , under the assumption that the density does not vanish too fast at zero and decays at least as exp --|x| $ρ$ , $ρ$ \textgreater{} 0, at infinity.

Weak and Strong disorder for the stochastic heat equation and the continuous directed polymer in $d\geq 3$

We consider the smoothed multiplicative noise stochastic heat equation $$d u_{\eps,t}= \frac 12 Δu_{\eps,t} d t+ β\eps^{\frac{d-2}{2}}\, \, u_{\eps, t} \, d B_{\eps,t} , \;\;u_{\eps,0}=1,$$ in dimension $d\geq 3$ , where $B_{\eps,t}$ is a spatially smoothed (at scale $\eps$) space-time white noise, and $β>0$ is a parameter. We show the existence of a $\barβ\in (0,\infty)$ so that the solution exhibits weak disorder when $β<\barβ$ and strong disorder when $β> \barβ$ . The proof techniques use elements of the theory of the Gaussian multiplicative chaos.

Convergence in law of the maximum of the two-dimensional discrete Gaussian free field

We consider the two-dimensional Gaussian Free Field on a box of side length $N$ , with Dirichlet boundary data, and prove the convergence of the law of the recentered maximum of the field.

Extremal eigenvalue fluctuations in the GUE minor process and the law of fractional logarithm

We consider the GUE minor process, where a sequence of GUE matrices is drawn from the corner of a doubly infinite array of i.i.d. standard normal variables subject to the symmetry constraint. From each matrix, we take its largest eigenvalue, appropriately rescaled to converge to the standard Tracy-Widom distribution. We show the analogue of the law of iterated logarithm for this sequence, i.e. we divide the normalized n-th eigenvalue by a logarithmic factor and show the limsup of this sequence is a constant almost surely. We also give almost sure bounds for the appropriately scaled liminf.

Large deviations for the two-dimensional two-component plasma

We derive a large deviations principle for the two-dimensional two-component plasma in a box. As a consequence, we obtain a variational representation for the free energy, and also show that the macroscopic empirical measure of either positive or negative charges converges to the uniform measure. An appendix, written by Wei Wu, discusses applications to the supercritical complex Gaussian multiplicative chaos.

Large deviations for zeros of random polynomials with i.i.d. exponential coefficients

We derive a large deviation principle for the empirical measure of zeros of random polynomials with i.i.d. exponential coefficients.

Freezing and decorated Poisson point processes

The limiting extremal processes of the branching Brownian motion (BBM), the two-speed BBM, and the branching random walk are known to be randomly shifted decorated Poisson point processes (SDPPP). In the proofs of those results, the Laplace functional of the limiting extremal process is shown to satisfy $L[θ_y f]=g(y-τ_f)$ for any nonzero, nonnegative, compactly supported, continuous function $f$ , where $θ_y$ is the shift operator, $τ_f$ is a real number that depends on $f$ , and $g$ is a real function that is independent of $f$ . We show that, under some assumptions, this property characterizes the structure of SDPPP. Moreover, when it holds, we show that $g$ has to be a convolution of the Gumbel distribution with some measure. The above property of the Laplace functional is closely related to a `freezing phenomenon' that is expected by physicists to occur in a wide class of log-correlated fields, and which has played an important role in the analysis of various models. Our results shed light on this intriguing phenomenon and provide a natural tool for proving an SDPPP structure in these and other models.

Matrix optimization under random external fields

We consider the quadratic optimization problem $F_n^{W,h}:= \sup_{x \in S^{n-1}} ( x^T W x/2 + h^T x )\,,$ with $W$ a (random) matrix and $h$ a random external field. We study the probabilities of large deviation of $F_n^{W,h}$ for $h$ a centered Gaussian vector with i.i.d. entries, both conditioned on $W$ (a general Wigner matrix), and unconditioned when $W$ is a GOE matrix. Our results validate (in a certain region) and correct (in another region), the prediction obtained by the mathematically non-rigorous replica method in Y. V. Fyodorov, P. Le Doussal, J. Stat. phys. 154 (2014).

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

We consider the following detection problem: given a realization of a symmetric matrix ${\mathbf{X}}$ of dimension $n$ , distinguish between the hypothesis that all upper triangular variables are i.i.d. Gaussians variables with mean 0 and variance $1$ and the hypothesis where ${\mathbf{X}}$ is the sum of such matrix and an independent rank-one perturbation. This setup applies to the situation where under the alternative, there is a planted principal submatrix ${\mathbf{B}}$ of size $L$ for which all upper triangular variables are i.i.d. Gaussians with mean $1$ and variance $1$ , whereas all other upper triangular elements of ${\mathbf{X}}$ not in ${\mathbf{B}}$ are i.i.d. Gaussians variables with mean 0 and variance $1$ . We refer to this as the `Gaussian hidden clique problem.' When $L=(1+ε)\sqrt{n}$ ( $ε>0$ ), it is possible to solve this detection problem with probability $1-o_n(1)$ by computing the spectrum of ${\mathbf{X}}$ and considering the largest eigenvalue of ${\mathbf{X}}$ . We prove that this condition is tight in the following sense: when $L<(1-ε)\sqrt{n}$ no algorithm that examines only the eigenvalues of ${\mathbf{X}}$ can detect the existence of a hidden Gaussian clique, with error probability vanishing as $n\to\infty$ . We prove this result as an immediate consequence of a more general result on rank-one perturbations of $k$ -dimensional Gaussian tensors. In this context we establish a lower bound on the critical signal-to-noise ratio below which a rank-one signal cannot be detected.

Performance of the Metropolis algorithm on a disordered tree: The Einstein relation

Consider a $d$ -ary rooted tree ( $d\geq3$ ) where each edge $e$ is assigned an i.i.d. (bounded) random variable $X(e)$ of negative mean. Assign to each vertex $v$ the sum $S(v)$ of $X(e)$ over all edges connecting $v$ to the root, and assume that the maximum $S_n^*$ of $S(v)$ over all vertices $v$ at distance $n$ from the root tends to infinity (necessarily, linearly) as $n$ tends to infinity. We analyze the Metropolis algorithm on the tree and show that under these assumptions there always exists a temperature $1/β$ of the algorithm so that it achieves a linear (positive) growth rate in linear time. This confirms a conjecture of Aldous [Algorithmica 22 (1998) 388-412]. The proof is obtained by establishing an Einstein relation for the Metropolis algorithm on the tree.

Regularization of non-normal matrices by Gaussian noise

We consider the regularization of matrices $M^N$ written in Jordan form by additive Gaussian noise $N^{-γ}G^N$ , where $G^N$ is a matrix of i.i.d. standard Gaussians and $γ>1/2$ so that the operator norm of the additive noise tends to $0$ with $N$ . Under mild conditions on the structure of $M^N$ we evaluate the limit of the empirical measure of eigenvalues of $M^N+N^{-γ} G^N$ and show that it depends on $γ$ , in contrast with the case of a single Jordan block.

Singular values of Gaussian matrices and permanent estimators

We present estimates on the small singular values of a class of matrices with independent Gaussian entries and inhomogeneous variance profile, satisfying a broad-connectedness condition. Using these estimates and concentration of measure for the spectrum of Gaussian matrices with independent entries, we prove that for a large class of graphs satisfying an appropriate expansion property, the Barvinok--Godsil-Gutman estimator for the permanent achieves sub-exponential errors with high probability.

Extreme values for two-dimensional discrete Gaussian free field

We consider in this paper the collection of near maxima of the discrete, two dimensional Gaussian free field in a box with Dirichlet boundary conditions. We provide a rough description of the geometry of the set of near maxima, estimates on the gap between the two largest maxima, and an estimate for the right tail up to a multiplicative constant on the law of the centered maximum.

Fluctuations of recentered maxima of discrete Gaussian Free Fields on a class of recurrent graphs

We provide conditions that ensure that the recentered maximum of the Gaussian free field on a sequence of graphs fluctuates at the same order as the field at the point of maximal variance. In particular, on a sequence of such graphs the recentered maximum is not tight, similarly to the situation in Z but in contrast with the situation in Z^2. We show that our conditions cover a large class of "fractal" graphs.

Localization for controlled random walks and martingales

We consider controlled random walks that are martingales with uniformly bounded increments and nontrivial jump probabilities and show that such walks can be constructed so that P(S_n^u=0) decays at polynomial rate n^{-α} where α>0 can be arbitrarily small. We also show, by means of a general delocalization lemma for martingales, which is of independent interest, that slower than polynomial decay is not possible.

Remarks on a constrained optimization problem for the Ginibre ensemble

We study the limiting distribution of the eigenvalues of the Ginibre ensemble conditioned on the event that a certain proportion lie in a given region of the complex plane. Using an equivalent formulation as an obstacle problem, we describe the optimal distribution and some of its monotonicity properties.

preprint2012arXiv

Maximal Arithmetic Progressions in Random Subsets

Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}^N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to an extreme type (asymmetric) distribution. The same result holds for the maximal length W(N) of arithmetic progressions (mod N). When considered in the natural way on a common probability space, we observe that U(N)/log(N) converges almost surely to 2/log(2), while W(N)/log(N) does not converge almost surely (and in particular, limsup W(N)/log(N) is at least 3/log(2)).

preprint2012arXiv

Slowdown for time inhomogeneous branching Brownian motion

We consider the maximal displacement of one dimensional branching Brownian motion with (macroscopically) time varying profiles. For monotone decreasing variances, we show that the correction from linear displacement is not logarithmic but rather proportional to $T^{1/3}$ . We conjecture that this is the worse case correction possible.

preprint2012arXiv

Tensor Products of Random Unitary Matrices

Tensor products of M random unitary matrices of size N from the circular unitary ensemble are investigated. We show that the spectral statistics of the tensor product of random matrices becomes Poissonian if M=2, N become large or M become large and N=2.

A conjecture concerning optimality of the Karhunen-Loeve basis in nonlinear reconstruction

We present a conjecture regarding the expectation of the maxima of $L^2$ norms of sub-vectors of a Gaussian vector; this has application to nonlinear reconstruction.

A sharp estimate for cover times on binary trees

We compute the second order correction for the cover time of the binary tree of depth $n$ by (continuous-time) random walk, and show that with probability approaching 1 as $n$ increases, $\sqrt{τ_{\mathrm{cov}}}=\sqrt{|E|}[\sqrt{2\log 2}\cdot n - {\log n}/{\sqrt{2\log 2}} + O((\log\logn)^8]$, thus showing that the second order correction differs from the corresponding one for the maximum of the Gaussian free field on the tree.

Branching Random Walks in Time Inhomogeneous Environments

We study the maximal displacement of branching random walks in a class of time inhomogeneous environments. Specifically, binary branching random walks with Gaussian increments will be considered, where the variances of the increments change over time macroscopically. We find the asymptotics of the maximum up to an $O_P(1)$ (stochastically bounded) error, and focus on the following phenomena: the profile of the variance matters, both to the leading (velocity) term and to the logarithmic correction term, and the latter exhibits a phase transition.

Convergence of the spectral measure of non normal matrices

We discuss regularization by noise of the spectrum of large random non-Normal matrices. Under suitable conditions, we show that the regularization of a sequence of matrices that converges in *-moments to a regular element $a$ , by the addition of a polynomially vanishing Gaussian Ginibre matrix, forces the empirical measure of eigenvalues to converge to the Brown measure of $a$ .

Einstein relation for biased random walk on Galton--Watson trees

We prove the Einstein relation, relating the velocity under a small perturbation to the diffusivity in equilibrium, for certain biased random walks on Galton--Watson trees. This provides the first example where the Einstein relation is proved for motion in random media with arbitrary deep traps.

Hard edge tail asymptotics

Let $Λ$ be the limiting smallest eigenvalue in the general (β, a)-Laguerre ensemble of random matrix theory. Here β>0, a >-1; for β=1,2,4 and integer a, this object governs the singular values of certain rank n Gaussian matrices. We prove that P(Λ> λ) = e^{- (β/2) λ+ 2 γλ^{1/2}} λ^{- (γ(γ+1))/(2β) + γ/4} E (β, a) (1+o(1)) as λgoes to infinity, in which γ= (β/2) (a+1)-1 and E(β, a) is a constant (which we do not determine). This estimate complements/extends various results previously available for special values of βand a.

Mixing times for random k-cycles and coalescence-fragmentation chains

Let $\mathcal{S}_n$ be the permutation group on $n$ elements, and consider a random walk on $\mathcal{S}_n$ whose step distribution is uniform on $k$ -cycles. We prove a well-known conjecture that the mixing time of this process is $(1/k)n\log n$ , with threshold of width linear in $n$ . Our proofs are elementary and purely probabilistic, and do not appeal to the representation theory of $\mathcal{S}_n$ .

On common roots of random Bernoulli polynomials

We prove that with high probability, d+1 random Bernoulli polynomials in d variables of degree n (n goes to infinity) do not possess a common root.

Quenched invariance principle for random walks in balanced random environment

We consider random walks in a balanced random environment in $\mathbb{Z}^d$ , $d\geq 2$ . We first prove an invariance principle (for $d\ge2$ ) and the transience of the random walks when $d\ge 3$ (recurrence when $d=2$ ) in an ergodic environment which is not uniformly elliptic but satisfies certain moment condition. Then, using percolation arguments, we show that under mere ellipticity, the above results hold for random walks in i.i.d. balanced environments.

Quenched limits for transient, zero speed one-dimensional random walk in random environment

We consider a nearest-neighbor, one dimensional random walk $\{X_n\}_{n\geq0}$ in a random i.i.d. environment, in the regime where the walk is transient but with zero speed, so that $X_n$ is of order $n^s$ for some $s<1$ . Under the quenched law (i.e., conditioned on the environment), we show that no limit laws are possible: There exist sequences $\{n_k\}$ and $\{x_k\}$ depending on the environment only, such that $X_{n_k}-x_k=o(\log n_k)^2$ (a localized regime). On the other hand, there exist sequences $\{t_m\}$ and $\{s_m\}$ depending on the environment only, such that $\log s_m/\log t_m\to s<1$ and $P_ω(X_{t_m}/s_m\leq x)\to1/2$ for all $x>0$ and $\to0$ for $x\leq0$ (a spread out regime).

Snake representation of a superprocess in random environment

We consider (discrete time) branching particles in a random environment which is i.i.d. in time and possibly spatially correlated. We prove a representation of the limit process by means of a Brownian snake in random environment.

Differing averaged and quenched large deviations for random walks in random environments in dimensions two and three

We consider the quenched and the averaged (or annealed) large deviation rate functions $I_q$ and $I_a$ for space-time and (the usual) space-only RWRE on $\mathbb{Z}^d$ . By Jensen's inequality, $I_a\leq I_q$ . In the space-time case, when $d\geq3+1$ , $I_q$ and $I_a$ are known to be equal on an open set containing the typical velocity $ξ_o$ . When $d=1+1$ , we prove that $I_q$ and $I_a$ are equal only at $ξ_o$ . Similarly, when d=2+1, we show that $I_a<I_q$ on a punctured neighborhood of $ξ_o$ . In the space-only case, we provide a class of non-nestling walks on $\mathbb{Z}^d$ with d=2 or 3, and prove that $I_q$ and $I_a$ are not identically equal on any open set containing $ξ_o$ whenever the walk is in that class. This is very different from the known results for non-nestling walks on $\mathbb{Z}^d$ with $d\geq4$ .

Recursions and tightness for the maximum of the discrete, two dimensional Gaussian Free Field

We consider the maximum of the discrete two dimensional Gaussian free field in a box, and prove the existence of a (dense) deterministic subsequence along which the maximum, centered at its mean, is tight; this still leaves open the conjecture that tightness holds without the need for subsequences. The method of proof relies on an argument developed by Dekking and Host for branching random walks with bounded increments and on comparison results specific to Gaussian fields.

Support convergence in the single ring theorem

We study the eigenvalues of non-normal square matrices of the form A_n=U_nT_nV_n with U_n,V_n independent Haar distributed on the unitary group and T_n real diagonal. We show that when the empirical measure of the eigenvalues of T_n converges, and T_n satisfies some technical conditions, all these eigenvalues lie in a single ring.

The single ring theorem

We study the empirical measure $L_{A_n}$ of the eigenvalues of non-normal square matrices of the form $A_n=U_nD_nV_n$ with $U_n,V_n$ independent Haar distributed on the unitary group and $D_n$ real diagonal. We show that when the empirical measure of the eigenvalues of $D_n$ converges, and $D_n$ satisfies some technical conditions, $L_{A_n}$ converges towards a rotationally invariant measure on the complex plan whose support is a single ring. In particular, we provide a complete proof of Feinberg-Zee single ring theorem \cite{FZ}. We also consider the case where $U_n,V_n$ are independent Haar distributed on the orthogonal group.

Tightness of Fluctuations of First Passage Percolation on Some Large Graphs

The theorem of Dekking and Host regarding tightness around the mean of first passage percolation on the binary tree, from the root to a boundary of a ball, is generalized to a class of graphs which includes all lattices in hyperbolic spaces and the lamplighter graph over N. This class of graphs is closed under product with any bounded degree graph. Few open problems and conjectures are gathered at the end.