Computer Science/Discrete Mathematics Seminar I

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.