|COMPUTER SCIENCE/DISCRETE MATH II|
|Topic:||Balancing Gaussian Vectors|
|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.