CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Math Colloquium
Kevin Costello
Georgia Institute of Technology
Title: Littlewood-Offord type problems and the rank of random symmetric matrices

Abstract: Let f(x_1, ..., x_n) be a polynomial dependent on a large number of independent random variables and having many nonzero coefficients. A natural question to ask is how dispersed the output of f becomes as the number of variables increases. To be more concrete: Suppose each x_i is independently set equal to 1 or -1. What is the maximum concentration of such an f on any single value, and what polynomials come close to achieving this concentration? The case where f is linear was first investigated by Littlewood and Offord and solved by Erdos: The maximal concentration of O(n^{-1/2}) occurs when the nonzero coefficients of f are all equal. Here I will describe some near-tight bounds for the case where f is a bilinear or quadratic form. As an application, I will give a bound(joint with Tao and Vu) on the probability that a random symmetric matrix is singular.

Date: Friday, February 20, 2009
Time: 4:30 pm
Location: Wean Hall 7500