TR07-086 Authors: Venkatesan Guruswami, James R. Lee, Alexander Razborov

Publication: 11th September 2007 14:58

Downloads: 3069

Keywords:

We give an explicit (in particular, deterministic polynomial time)

construction of subspaces $X

\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,

$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$

If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits

and $\dim(X) \geq (1-\eta)N$ for any fixed constant $\eta$, the lower bound

can be further improved to $(\log N)^{-O(1)} \sqrt{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.