Expander codes, distortion, and pseudorandom subspaces
Speaker: James R. Lee , University of Washington
Date: December 11 2007
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Piotr Indyk, MIT, CSAIL
Contact: Alexandr Andoni, 617-253-6182, toc-seminar-planners@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/theory-seminars/calendar.html
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 compressive 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, with guest appearances by: Ramanujan graphs, sum-product theorems in finite fields, and mutually unbiased bases. I will also explain how these constructions lead to explicit compressive sensing matrices, and explicit error-correcting codes over the reals, with some advantages over random constructions.
Joint work with Venkat Guruswami and Sasha Razborov.
See other events that are part of Theory Colloquium Fall 2007
See other events happening in December 2007
