<p>A classic result provable by bootstrapping (and applicable to proving real lower bounds) is that in any computational model where we have <span class="math-container">$TIME(n) \neq TIME(n^c)$</span> for <em>some</em> constant <span class="math-container">$c &gt; 1$</span>, we in fact have  <span class="math-container">$TIME(n) \neq TIME(n^{1+\epsilon})$</span>, for every <span class="math-container">$\epsilon &gt; 0$</span>.</p>

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

CC BY-SA 4.0
2019-07-10T00:28:49.333Z
That’s a lovely example! IIRC the nondeterministic time hierarchy theorem is proved this way at the very beginning (by Cook?).
Lwins
CC BY-SA 4.0
2019-07-11T22:29:49.670Z
That's more-or-less true. In a typical application of the above argument we can only apply it a "constant" number of times; Cook shows how to apply it an "unbounded" number of times
Ryan Williams
CC BY-SA 4.0
2019-07-09T06:01:15.893Z
2019-07-09T06:01:15.893Z
Ryan Williams
<p>I'm not sure if this counts because it's all from the same paper, but in <a href="https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf" rel="noreferrer">Craig Gentry's first pass at fully homomorphic encryption based on ideal lattices</a>, 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.</p>

CC BY-SA 4.0
2019-07-08T08:11:36.503Z
2019-07-08T08:11:36.503Z
Yonatan N
<p>Huang's recent proof of <span class="math-container">$A'$</span>, the Sensitivity Conjecture, involved proving an <span class="math-container">$A$</span> known to imply it. See Aaronson's blog:</p>

<p>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 <span class="math-container">$A$</span>:</p>

<blockquote>
  <p>Let S be any subset of the n-dimensional Boolean hypercube, <span class="math-container">$\{0,1\}^n$</span>, which has size <span class="math-container">$2^{n-1}+1$</span>. Then there must be a point in S with at least ~nc neighbors in S.</p>
</blockquote>

CC BY-SA 4.0
2019-07-07T01:36:58.560Z
2019-07-08T08:54:19.713Z
2019-07-08T08:54:19.713Z
Bjørn Kjos-Hanssen
<p>One thing that comes to mind, in computational learning theory, is <em>boosting</em>. Essentially:</p>

<blockquote>
  <p>In the PAC setting, if you have a weak learner for class <span class="math-container">$\mathcal{C}$</span> (i.e., something doing "merely better" than random guessing), then you obtain a (strong) learner for class <span class="math-container">$\mathcal{C}$</span>.</p>
</blockquote>

<p>Typically, this is indeed used by obtaining a weak learner.</p>

CC BY-SA 4.0
2019-07-10T01:07:08.913Z
2019-07-10T01:07:08.913Z
Clement C.
<p>There is a type of results in TCS usually called <em>bootstrapping results</em>. In general, it is of the form</p>

<blockquote>
  <p>If proposition <span class="math-container">$A$</span> holds, then proposition <span class="math-container">$A'$</span> holds.</p>
</blockquote>

<p>where <span class="math-container">$A$</span> and <span class="math-container">$A'$</span> are propositions that look similar, and <span class="math-container">$A$</span> is seemingly "weaker" then <span class="math-container">$A'$</span>, which is the reason we name this type of results.
Let me give a few concrete examples:</p>

<blockquote>
  <p><strong>Theorem.</strong> <a href="https://eccc.weizmann.ac.il/report/2018/199/download" rel="nofollow noreferrer">[Chen and Tell, STOC'19]</a> Fix any problem <span class="math-container">$\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$</span>
  . Assume that for every <span class="math-container">$c&gt;1$</span> there exist infinitely many <span class="math-container">$d\in \mathbb{N}$</span> such that <span class="math-container">$\mathcal{TC}^0$</span> circuits of depth <span class="math-container">$d$</span> need more than <span class="math-container">$n^{1+c^{-d}}$</span> wires to solve the problem <span class="math-container">$\Pi$</span>. Then for any <span class="math-container">$d_0,k \in \mathbb{N}$</span>, <span class="math-container">$\Pi$</span> cannot be solved by <span class="math-container">$\mathcal{TC}^0$</span> circuits of depth <span class="math-container">$d_0$</span> and <span class="math-container">$n^k$</span> wires, and therefore <span class="math-container">$\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$</span>.</p>
  
  <p><strong>Theorem.</strong> <a href="https://eccc.weizmann.ac.il/report/2013/026/download/" rel="nofollow noreferrer">[Gupta et al., FOCS'13]</a> Suppose that computing the permanent requires depth-<span class="math-container">$3$</span> arithmetic circuits of size more than <span class="math-container">$n^{\Omega(\sqrt{n})}$</span>, over fields of characteristic <span class="math-container">$0$</span>. Then computing the permanent requires arithmetic circuits of superpolynomial size, and therefore Valiant's Conjecture holds.</p>
</blockquote>

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

<blockquote>
  <p><strong>Theorem.</strong> <a href="https://arxiv.org/abs/1412.0348" rel="nofollow noreferrer">[Backurs and Indyk, STOC'15]</a> If we can compute EDIT DISTANCE in <span class="math-container">$O(n^{2-\epsilon})$</span> time (on the RAM model), then we will get a SAT solver faster than any one that currently exists.</p>
</blockquote>

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

<p>As you may have imagined, (to my  best knowledge) <em>all</em> 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.</p>

<p>Usually there are two ways to understand a bootstrapping result. 1. We only need to prove <span class="math-container">$A$</span> and then apply the result, if we want to prove <span class="math-container">$A'$</span>; 2. Proving <span class="math-container">$A$</span> may be difficult because <em>a priori</em> we <em>think</em> proving <span class="math-container">$A'$</span> difficult.</p>

<p>The problem is that, one (or more exactly, <em>I</em>) 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</p>

<blockquote>
  <p>Do we know any bootstrapping result in which <span class="math-container">$A$</span> is proven?</p>
</blockquote>

CC BY-SA 4.0
2019-07-10T00:52:41.443Z
Would boosting (loosely speaking: "if you have a PAC-weak learner, you have a PAC-learner") fit the bill?
Clement C.
CC BY-SA 4.0
2019-07-10T00:57:39.177Z
@ClementC. Sure. Your comment reminds me of some fundamental results in cryptography, like, “one-way functions imply pseudorandom function families”
Lwins
<cc.complexity-theory>
Bootstrapping results that really bootstrap
Lwins
# Bootstrapping results that really bootstrap

(Asked by: username_0 on 2019-07-07)

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]](https://eccc.weizmann.ac.il/report/2018/199/download) 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]](https://eccc.weizmann.ac.il/report/2013/026/download/) 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]](https://arxiv.org/abs/1412.0348) 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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Would boosting (loosely speaking: "if you have a PAC-weak learner, you have a PAC-learner") fit the bill?  
> **username_0**: @ClementC. Sure. Your comment reminds me of some fundamental results in cryptography, like, “one-way functions imply pseudorandom function families”  

---

## 4 answers

### Answer by username_2 on 2019-07-09. Score: 10

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.

> **Comments:**
> **username_0**: That’s a lovely example! IIRC the nondeterministic time hierarchy theorem is proved this way at the very beginning (by Cook?).  
> **username_2**: That's more-or-less true. In a typical application of the above argument we can only apply it a "constant" number of times; Cook shows how to apply it an "unbounded" number of times  

---

### Answer by username_3 on 2019-07-08. Score: 5

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](https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf), 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 by username_4 on 2019-07-07. Score: 4

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 by username_1 on 2019-07-10. Score: 3

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.


---

