# Expander Codes and Somewhat Euclidean Expllicit Sections

 COMPUTER SCIENCE/DISCRETE MATH I Topic: Expander Codes and Somewhat Euclidean Expllicit Sections Speaker: Alexander Razborov Affiliation: Member and School of Mathematics Date: Tuesday, May 22 Time/Room: 10:30am - 12:30pm/West Building Lecture Theatre

This talk is devoted to linear subspaces of $R^N$ on which $\ell_1$ and $\ell_2$-norms are closed to each other (up to the obvious normalizing factor $N^{1/2}$). Such sections'' are important e.g. in the theory of metric embeddings, and for many reasons it is highly desirable to be able to construct them explicitly. But although several probabilistic constructions were given before, if we insist on "fully explicitness", nothing seems to have been known when the dimension of the constructed subspace is required to be proportional to $N$. We propose to use for this purpose straightforward analogues in characteristic 0 of so-called Expander Codes. We show that bipartite graphs with exceptionally good (and not attained so far by an explicit construction) expansion properties do lead to sections of dimension (say) $N/2$ and with "distortion"' $N^{o(1)}$. In particular, our result provides yet one more motivation for the search of explicit expander graphs with improved expansion properties.