ALMOST EUCLIDEAN SUBSPACES OF l1N VIA EXPANDER CODES

被引：10

作者：

Guruswami, Venkatesan ^{[1
,2
]}

Lee, James R. ^{[2
]}

Razborov, Alexander ^{[3
,4
]}

机构：

[1] Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA

[2] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA

[3] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA

[4] VA Steklov Math Inst, Moscow 117966, Russia

来源：

COMBINATORICA | 2010年 / 30卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

RANDOMNESS; EMBEDDINGS; SECTIONS; GRAPHS; FIELDS;

D O I：

10.1007/s00493-010-2463-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X subset of R-N of dimension (1-o(1))N such that for every x is an element of X, (log N)(-O(log log log N)) root N parallel to x parallel to(2) <= parallel to x parallel to(1) <= root N parallel to x parallel to(2). If we are allowed to use N-1/log log N <= N degrees((1)) random bits and dim(X) >= (1-eta)N for any fixed constant eta, the lower bound can be further improved to (log N)(-O(1))root N parallel to x parallel to(2).

引用

页码：47 / 68

页数：22