We introduce a new approach to construct extractors -- combinatorial objects akin to expander graphs that have several applications. Our approach is based on error correcting codes and on the Nisan-Wigderson pseudorandom generator. An application of our approach yields a construction that is simple to describe and analyze, does not ... more >>>

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

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

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to: (1) Constant degree dimension expanders in finite ... more >>>

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a distribution $X$ on binary strings of length $n$ is a $\delta$-source if $X$ assigns probability at most $2^{-\delta n}$ to any string of length $n$. For every $\delta>0$ we construct the following poly($n$)-time ... more >>>