[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR
 
 
Tuesday, May 14, 2013
3:00 p.m.
Ryerson 251
 
Van Vu
Rutgers University
www.math.rutgers.edu/~vanvu/
 
Title:  “Anti-concentration results and applications”
 
Abstract: 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)
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130508/d6497b11/attachment.htm