Computer Science/Discrete Mathematics Seminar II

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.