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.