Speaker: Venkatesan Guruswami Title: Compressed Sensing, Euclidean sections, and JL lemma Abstract: I will discuss the compressed sensing problem, which has received a lot of attention in diverse communities in the last 4-5 years. (The repository at Rice University http://www.dsp.ece.rice.edu/cs/ gives an idea of the volume of recent work this problem has attracted.) In this talk, I will focus on connections of this problem to two classical themes in high-dimensional geometry: (i) Euclidean sections (or low-distortion embeddings of \ell_2 into \ell_1), and (ii) the Johnson-Lindenstrauss lemma and restricted isometry. I might also discuss some recent work on constructing explicit/derandomized Euclidean sections and compressed sensing matrices using expander graphs.