Bootstrapping results that really bootstrap

Question

There is a type of results in TCS usually called bootstrapping results. In general, it is of the form

If proposition $A$ holds, then proposition $A'$ holds.

where $A$ and $A'$ are propositions that look similar, and $A$ is seemingly "weaker" then $A'$, which is the reason we name this type of results. Let me give a few concrete examples:

Theorem. [Chen and Tell, STOC'19] Fix any problem $\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$ . Assume that for every $c>1$ there exist infinitely many $d\in \mathbb{N}$ such that $\mathcal{TC}^0$ circuits of depth $d$ need more than $n^{1+c^{-d}}$ wires to solve the problem $\Pi$. Then for any $d_0,k \in \mathbb{N}$, $\Pi$ cannot be solved by $\mathcal{TC}^0$ circuits of depth $d_0$ and $n^k$ wires, and therefore $\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$.

Theorem. [Gupta et al., FOCS'13] Suppose that computing the permanent requires depth-$3$ arithmetic circuits of size more than $n^{\Omega(\sqrt{n})}$, over fields of characteristic $0$. Then computing the permanent requires arithmetic circuits of superpolynomial size, and therefore Valiant's Conjecture holds.

Well, a more famous but not-so-appropriate example comes from fine-grained complexity:

Theorem. [Backurs and Indyk, STOC'15] If we can compute EDIT DISTANCE in $O(n^{2-\epsilon})$ time (on the RAM model), then we will get a SAT solver faster than any one that currently exists.

Update. (July 10, 2019) The edit distance example may be a little confusing. Refer to Ryan’s answer for a “standard” example.

As you may have imagined, (to my best knowledge) all results of this type are proved by taking the contrapositive (I have taken the contrapositive in the edit distance one). So in some sense these are all algorithmic results.

Usually there are two ways to understand a bootstrapping result. 1. We only need to prove $A$ and then apply the result, if we want to prove $A'$; 2. Proving $A$ may be difficult because a priori we think proving $A'$ difficult.

The problem is that, one (or more exactly, I) may be hardly optimistic and take the first understanding, if there does not exist any positive use of bootstrap results after all! So my question is

Do we know any bootstrapping result in which $A$ is proven?

Answer 1

A classic result provable by bootstrapping (and applicable to proving real lower bounds) is that in any computational model where we have $TIME(n) \neq TIME(n^c)$ for some constant $c > 1$, we in fact have $TIME(n) \neq TIME(n^{1+\epsilon})$, for every $\epsilon > 0$.

The idea is that if $TIME(n) = TIME(n^{1+\epsilon})$, we can apply a padding argument repeatedly to obtain $TIME(n) = TIME(n^c)$ for every constant $c$. You can even use such an argument to slightly improve known time hierarchy theorems in various cases.

Answer 2

I'm not sure if this counts because it's all from the same paper, but in Craig Gentry's first pass at fully homomorphic encryption based on ideal lattices, he first shows that in order to construct a FHE scheme, it suffices to construct a "somewhat homomorphic" encryption scheme with a certain property (its decryption circuit is shallower than the depths the circuit can encrypt). He then, with a lot of work, shows how to construct such a somewhat homomorphic encryption scheme.

Answer 3

Huang's recent proof of $A'$, the Sensitivity Conjecture, involved proving an $A$ known to imply it. See Aaronson's blog:

From pioneering work by Gotsman and Linial in 1992, it was known that to prove the Sensitivity Conjecture, it suffices to prove the following even simpler combinatorial conjecture $A$:

Let S be any subset of the n-dimensional Boolean hypercube, $\{0,1\}^n$, which has size $2^{n-1}+1$. Then there must be a point in S with at least ~nc neighbors in S.

Answer 4

One thing that comes to mind, in computational learning theory, is boosting. Essentially:

In the PAC setting, if you have a weak learner for class $\mathcal{C}$ (i.e., something doing "merely better" than random guessing), then you obtain a (strong) learner for class $\mathcal{C}$.

Typically, this is indeed used by obtaining a weak learner.