The spectral edge of some random band matrices (2009)
We study the asymptotic distribution of the eigenvalues of random Hermitian periodic band matrices, focusing on the spectral edges. The eigenvalues close to the edges converge in distribution to the...
The Tracy--Widom law for some sparse random matrices (2009)
Consider the random matrix obtained from the adjacency matrix of a random d-regular graph by multiplying every entry by a random sign. The largest eigenvalue converges, after proper scaling, to the...
Poisson asymptotics for random projections of points on a high-dimensional sphere (2009)
Benjamini, Itai, Schramm, Oded, Sodin, Sasha
Project a collection of points on the high-dimensional sphere onto a random direction. If most of the points are sufficiently far from one another in an appropriate sense, the projection is locally...
One more proof of the Erd\H{o}s--Tur\'an inequality, and an error estimate in Wigner's law (2009)
Feldheim, Ohad N., Sodin, Sasha
We prove the Erdos-Turan equidistribution inequality, using a construction due to Chebyshev, Markov, and Stieltjes. The method is applicable in a more general setting. As an example, we state another...
A universality result for the smallest eigenvalues of certain sample covariance matrices (2008)
Feldheim, Ohad N., Sodin, Sasha
After proper rescaling and under some technical assumptions, the smallest eigenvalue of a sample covariance matrix with aspect ratio bounded away from 1 converges to the Tracy--Widom distribution....
An extension of a Bourgain--Lindenstrauss--Milman inequality (2007)
Let || . || be a norm on R^n. Averaging || (\eps_1 x_1, ..., \eps_n x_n) || over all the 2^n choices of \eps = (\eps_1, ..., \eps_n) in {-1, +1}^n, we obtain an expression ||| . ||| which is an...
Bounds on the concentration function in terms of Diophantine approximation (2007)
We demonstrate a simple analytic argument that may be used to bound the Levy concentration function of a sum of independent random variables. The main application is a version of a recent inequality...
An isoperimetric inequality for uniformly log-concave measures and uniformly convex bodies (2007)
We prove an isoperimetric inequality for the uniform measure on a uniformly convex body and for a class of uniformly log-concave measures (that we introduce). These inequalities imply (up to...
Random matrices, non-backtracking walks, and orthogonal polynomials (2007)
Several well-known results from the random matrix theory, such as Wigner's law and the Marchenko--Pastur law, can be interpreted (and proved) in terms of non-backtracking walks on a certain graph....
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits (2007)
It is well known that R^N has subspaces of dimension proportional to N on which the \ell_1 norm is equivalent to the \ell_2 norm; however, no explicit constructions are known. Extending earlier work...
Non-backtracking random walks mix faster (2006)
Alon, Noga, Benjamini, Itai, Lubetzky, Eyal, Sodin, Sasha
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as...
An isoperimetric inequality on the $\ell_p$ balls (2006)
The normalised volume measure on the $\ell_p^n$ unit ball ($1\leq p\leq 2$) satisfies the following isoperimetric inequality: the boundary measure of a set of measure $a$ is at least...
Polynomial bounds for large Bernoulli sections of $\ell_1^N$ (2006)
Artstein-Avidan, Shiri, Friedland, Omer, Milman, Vitali, Sodin, Sasha
We prove a quantitative version of the bound on the smallest singular value of a Bernoulli covariance matrix (due to Bai and Yin). Then we use this bound, together with several recent developments,...
Non-backtracking random walks mix faster (2006)
Noga Alon, Itai Benjamini, Eyal Lubetzky, Sasha Sodin
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as...
Tail-sensitive Gaussian asymptotics for marginals of concentrated measures in high dimension (2005)
If the Euclidean norm is strongly concentrated with respect to a measure, the average distribution of an average marginal of this measure has Gaussian asymptotics that captures tail behaviour. If the...