Almost Euclidean subspaces of \ell_1^N via expander codes

Venkatesan Guruswami, James R. Lee, Alexander Razborov

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X of R^N of dimension (1-o(1))N such that for every element x in X, |x|_1 and N^{1/2} |…