ECCC - TR06-126

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR06-126 | 2nd October 2006 00:00

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

Contact

Add Comment

TR06-126 Authors: Piotr Indyk
Publication: 2nd October 2006 05:13
Downloads: 2926

Keywords:

discrete uncertainty principles, explicit constructions, geometric aspects of functional analysis, low-distortion embeddings, normed spaces, Randomness Extractors

Abstract:

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

ISSN 1433-8092 | Imprint