Type of Talk: UTCS Colloquium/ACT Seminar

Speaker Name/Affilliation: Venkatesan Guruswami/University of Washington &
IAS

Date: Friday November 9 2007

Start Time: 11:00a.m.-N

oon

Location: ACES 3.408

Host: Adam Klivans

Talk Tit

le: Expander codes pseudorandom matrices and Euclidean sections of L_1<

br>
Talk Abstract:
Classical results in high-dimensional geometry sta

te that in a random
subspace of R%5EN of dimension O(N) the L_1 and L_2
norms of every
vector differ by a Theta(%5Csqrt%7BN%7D) factor (so each
vector has its mass
spread nearly evenly over a constant fraction of t

he coordinates).
Indeed this is a particular example of the use of the
probabilistic
method a technique which is ubiquitous in asymptotic ge

ometric
analysis. Similar randomized geometric constructions arise
i

n areas like dimensionality reduction and compressed sensing
but it se

ems that such objects are very hard to come by explicitly.

We will d

escribe constructions inspired by expander codes
that can be used to ex

plicitly produce subspaces with distortion
nearly as good as a random s

ubspace. Specifically we construct
an explicit subspace X of R%5EN of
dimension N(1-o(1)) such that
every unit vector in X has L_1 norm at l

east (almost) sqrt%7BN%7D/poly
(log N). We will also discuss connection

s to sparse signal recovery
(i.e. compressed sensing). The technical i

ngredients in our work
include Ramanujan graphs sum-product theorems i

n finite fields
and Kerdock codes/ mutually unbiased bases.

%5B

This is joint work with James Lee and Alexander Razborov%5D