32
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ To clarify, you're not interested in cases where existence is proved by Borsuk-Ulam, or combinatorial Nullstellensatz, or pigeonhole, but only by probabilistic methods? $\endgroup$ – Timothy Chow Dec 27 '15 at 19:32
  • 4
    $\begingroup$ Even in the case of coding theory the algebraic-geometry methods work only for some parameter choices. For example the best asymptotic bounds known for self-dual binary codes are still probabilistic. $\endgroup$ – Noam D. Elkies Dec 27 '15 at 19:48
  • $\begingroup$ @TimothyChow Only probabilistic methods.. it will be good to get some opinion on this as well mathoverflow.net/questions/227062/… $\endgroup$ – T.... Dec 27 '15 at 20:14
  • $\begingroup$ @NoamD.Elkies i did not know and that sounds interesting.. also I think many other results from probabilistic number theory should fall here $\endgroup$ – T.... Dec 27 '15 at 20:15
  • $\begingroup$ @NoamD.Elkies Actually even for small alphabet it is not constructivised. $\endgroup$ – T.... Apr 7 '16 at 21:37
24
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ While there definitely are open questions about deterministically constructing matrices with the RIP property in polynomial time, I think this paper resolves the question of a deterministic JL lemma in time polynomial in $m$ cs.cmu.edu/~odonnell/papers/eio02.pdf. The issue with using this for constructing RIP matrices is that you would need it for an implicit $S$: the union of $k$-dimensional coordinate subspaces. $\endgroup$ – Sasho Nikolov Dec 28 '15 at 16:12
  • $\begingroup$ @SashoNikolov thank you for the link. $\endgroup$ – T.... Dec 29 '15 at 1:04
15
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This should be probably united with the answer by Thomas Kalinowski. $\endgroup$ – Fedor Petrov Dec 30 '15 at 4:34
7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.