Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-086 | 7th September 2007 00:00

Almost Euclidean subspaces of $\ell_1^N$ via expander codes

RSS-Feed




TR07-086
Authors: Venkatesan Guruswami, James R. Lee, Alexander Razborov
Publication: 11th September 2007 14:58
Downloads: 1706
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint