The Johnson–Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved (a set of $n$ points in high
dimensional Euclidean space can be mapped into an $O(\log (n)/ \varepsilon^2)$-dimensional Euclidean space such that the distance between any two points changes by only a factor of $1 \overset{+}{-} \varepsilon)$. 
A well-known proof of this exploits the phenomenon of concentration of measure and involves, in a sense, a probabilistic argument (Gaussian random matrices).
Does there exist a non-probabilistic proof of this lemma? 



Non-probabilistic proof of the Johnson–Lindenstrauss lemma
You might be interested in something Jelani Nelson wrote me in an email on Oct. 13, 2011:


"Another notion of derandomizing JL is the following: come up with a
distribution over embeddings that can be sampled using as few random
bits as possible so that, for any vector $x$ in $R^d$, a random vector has
its $\ell\_2$ norm preserved up to $1+\epsilon$ with probability $1-\delta$ by a
random embedding from that distribution (embedding into
$O(\epsilon^{-2}\log(1/\delta))$ dimensions). Existentially, it can be shown
that there exists such a distribution which can be sampled from using
$O(log(d/\delta))$ random bits. An actual explicit such distribution
would imply the two works above, since our deterministic algorithm
could just try all embeddings in the support of the distribution
(there would be poly$(d/\delta)$ of them) and take the best one, with
$\delta = 1/n^2$.


Obtaining a distribution that can be sampled using $O(\log(d/\delta))$
random bits is open. The best we have to date are:


-- Daniel M. Kane, Raghu Meka, Jelani Nelson: Almost Optimal Explicit
Johnson-Lindenstrauss Families. APPROX-RANDOM 2011: 628-639. (requires
$O(\log d + \log(1/\delta)\*\log\log(1/\delta) + \log(1/\delta)\log(1/\epsilon))$
random bits)


-- Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension
Reduction and Its Applications. IEEE Conference on Computational
Complexity 2011: 262-272. (requires $(1+o(1))\log d +
O(\log(1/(\epsilon\delta))$ random bits).


In fact, combining the approaches of both works can get $(1+o(1))\log d
+ O(\log(1/\delta)\log\log(1/\delta) + \log(1/\delta)\log(1/\epsilon))$."


I suggest contacting Jelani directly if you want more information.


