Seminar: May 14

Van Vu, Yale University

Anti-concentration results and applications

Consider the random sum S= c_1 x_1 +...+c_n x_n where c_i are real coefficents and x_i are iid random variables. Let I be a small interval.  About 8 years ago, Tao and the speaker made the following observation: Unless the coefficients c_i have a strong structure, the probability that S belongs to I  is very small.  We call results of this type anti-concentration theorems. 

As a motivation, let us mention a classical  result of Sarkoky and Szemeredi from the 1970s. Consider the case when  c_i=1 and x_i are iid Bernoulli random variables (taking value +-1). The probability that S equals zero is of order n^{-1/2} if n is even. However, if we forbid the c_i to be the same, then the probability that S is zero is  at most n^{-3/2}.  

We are going to discuss several anti-concentration results, which give the precise structure of the c_i.  As applications, we show that these results are essential in bounding the least singular value of random matrices (or randomly perturbed matrices in general).  The least singular value, in turn, plays a big role in smoothed analysis  and  the proof of the famous circular law conjecture  from random matrix theory. 

Joint work with H. Nguyen (OSU) and T. Tao (UCLA).