Balancing Gaussian Vectors

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Balancing Gaussian Vectors
Speaker:Kevin Costello
Affiliation:Rutgers, The State University of New Jersey
Date:Tuesday, October 30
Time/Room:10:30am - 12:30pm/S-101

Let ||.|| be any norm on R^d. We consider the question of estimating the minimum over all possible sign sequences e_i=+/-1 of ||e_1 x_1 + e_2 x_2 + ... + e_n x_n||, where the x_i are independent Gaussian vectors on R^d (here d is viewed as fixed and n as tending to infinity). The main result will be that in most cases this minimum will tend to be exponentially small in n, and that its distribution can be determined precisely.