Friday September 14th
WEH 7220, 3:30pm
TITLE: Expander codes and pseudorandom subspaces of R^n
James R. Lee
University of Washington
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. 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]
