Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with distortion:
TR07-086 | 7th September 2007
Venkatesan Guruswami, James R. Lee, Alexander Razborov

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

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 ... more >>>

ISSN 1433-8092 | Imprint