TIME: 1:30-2:20 pm, October 2, 2007 PLACE: MGH 295 SPEAKER: James Lee University of Washington TITLE: Expander codes, compressed sensing, and pseudorandom matrices ABSTRACT: Classical results in high-dimensional geometry state that on a random subspace of R^n of proportional dimension, the L_1 and L_2 norms are equivalent up to universal factors. Indeed, this is a particular example of the use of the probabilistic method, a technique which is now ubiquitous in asymptotic convex geometry. Similar randomized geometric constructions arise in areas like high-dimensional nearest-neighbor search and compressed sensing, but it seems that such objects are very hard to come by explicitly. I will show how constructions inspired by expander codes can be used to explicitly produce subspaces that are nearly as good as random for some of the problems discussed above. I will also show how distortion is directly related to sparse signal recovery (i.e. compressed sensing). Guest appearances by: Ramanujan graphs, sum-product theorems in finite fields, and mutually unbiased bases. [This is based on joint work with Venkat Guruswami and Sasha Razborov]