Almost Euclidean subspaces of e N 1 via expander codes
Venkatesan Guruswami, James R. Lee, Alexander Alexandrovich Razborov · Symposium on Discrete Algorithms · 2008
We give an explicit (in particular, deterministic polynomial time) construction of subspaces X ⊆ ℝN of dimension (1 - o(1))N such that for every x ∈ X, {display equation}. If we are allowed to use N1/log log N ≤ N°(1) random bits and dim(X) ≥ (1 - η)N for any fixed constant η, the lower bound can be further improved to (log N)-°(1) √N||x||2. Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes.