List of proofs where existence through probabilistic method has not been constructivised

Question

The probabilistic method as first pioneered by Erdős (although others have used this before) shows the existence of a certain object. What are some of the most important objects for which we can show the existence by such a method but constructive progress (construction in polynomial time) has been very hard to come by?

An important example is the existence of good codes in coding theory. Using algebraic geometry we can show such objects not only exist but can be constructed in polynomial time.

I am thinking that in addition to graph theoretic and direct combinatorial examples, there should be plenty of natural but very difficult examples from number theory and geometry as well.

Answer 1

There is an example of this which is important in machine learning: finding linear maps with the restricted isometry property. Given a set $S$ of $m$ points in $\mathbb{R}^N$ (with $N$ very large) and $\varepsilon > 0$, the problem is to find a linear map $L \colon \mathbb{R}^N \to \mathbb{R}^n$ such that $n << N$ and:

$$(1 - \varepsilon)\left\| x - y \right\| \leq \left\| Lx - Ly \right\| \leq (1 + \varepsilon)\left\| x - y \right\|$$

for all $x, y \in S$. Verifying that a given linear map has this property is NP-hard, but the orthogonal projection onto a random $n$-dimensional subspace (or even a $N \times n$ matrix whose entries are Gaussian random variables) has this property with high probability. This is the content of the Johnson-Lindenstrauss Lemma. In the full statement of the lemma the number $n$ can be chosen in a way which depends only on $m$ and $\varepsilon$ (not $N$).

See this paper for a more thorough discussion of the difficulties in finding more deterministic approaches to this specific problem. This paper also provides an attractive name for the general sort of phenomena that you're asking about: "finding hay in a haystack" (attributed to Avi Wigderson).

Answer 2

Lower bounds for Ramsey numbers might fit the bill. See for instance this question.

Answer 3

The number of explicit constructions of expander graphs is still limited. I haven't kept up with the latest developments but I think this one is still open:

Find a 16-regular multigraph on $n$ vertices whose second largest eigenvalue $\lambda_2<8$.

Existence follows from a deep probabilistic result of Joel Friedman. It's possible that one can turn Friedman's proof into a randomized polynomial time algorithm because one can certainly test whether $\lambda_2<8$ in polynomial time, but I don't think there is a deterministic polynomial time algorithm known.

Answer 4

A Ramsey graph is a graph on $n$ vertices that contains neither a clique nor an independent set of size $2\log_2 n$. Proving the existence of Ramsey graphs is easy using the probabilistic method, but there is no known polynomial time construction. Even the trick of generating a random graph and checking if it is a Ramsey graph doesn't work, because there is no known polynomial time algorithm for testing whether a given graph is Ramsey.

Answer 5

A family of permutations $T \subseteq S_n$ is called a $t$-wise permutation if its action on any $t$-tuple of elements is uniform. In other words, for any distinct elements $i_1, \cdots, i_t \in [n]$ and distinct elements $j_1, \cdots, j_t \in [n]$, $$ |\{ \pi ∈ T : \pi(i_1) = j_1, \cdots, \pi(i_t) = j_t \} | = \frac{1}{n(n − 1)· · ·(n − t + 1)}|T|.$$

In particular, for fixed $t$, $|T|$ must be of size at least $\sim n^t$. For $t \ge 4$, the only known construction of a $t$-wise permutation is of size $t^{2n}$ (see this elementary work by Finucane, Peled, and Yaari). Recently, Kuperberg, Lovett and Peled have proved the following strong result:

For all integers $n \ge 1$ and $1 \le t \le n$ there exists a $t$-wise permutation $T \subset S_n$ satisfying $|T| ≤ (cn)^{ct}$ for some universal constant $c > 0$.

Their proof is probabilistic, and involves a careful study of a carefully constructed random walk. Their paper contains other examples, such as designs and orthogonal arrays.

As far as I understand, having a constructive such family of permutations (or other structures described in the paper) can be applied in turning randomized algorithms into deterministic algorithms.

Answer 6

There are many properties of real numbers which hold a.e. with respect to Lebesgue measure, but are hard to check for specific numbers. A quick example.

Take a random number $x$ in $(0,1)$. Then for a given $p>1$ we may take its $p$-expansion $x=\sum_{i>0} a_{i,p}(x)p^{-i}$, $0\leq a_{i,p}(x)\leq p-1$. Digits $a_{i,p} (x)$ are independent and distributed uniformly on $\{0,1,\dots,p-1\}$. Hence by law of large numbers a.e. $x$ satisfy $$\lim_{N\rightarrow \infty} \frac1N \left|i\leq N: a_{i,p}(x)=c\right|=\frac 1p$$ for any given $c\in \{0,1,\dots,p-1\}$.

But there is no specific $x$ for which this is proved to hold simultaneosly for $p=2$ and $p=3$.

Answer 7

It depends a lot what you exactly you mean by "constructive". You can replace randomization by a greedy algorithm, or by a deterministic strategy similar to the one developed by Beck for combinatorial games (Combinatorial games: Tic-Tac-Toe theory, Encyclopedia of Mathematics and its Applications, Cambridge university press). This results in deterministic algorithms with running times similar to the naive test procedure, so if you want to have one graph colouring of a fixed graph avoiding certain monochromatic substructures, randomization does not help too much.

However, you do not get any structural understanding of the construction, nor do you get the existence for all $n$.