<p>It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon&gt;0$  then $BPP = P$ (<a href="https://dl.acm.org/citation.cfm?id=258590" rel="nofollow noreferrer">https://dl.acm.org/citation.cfm?id=258590</a>).</p>

<p>(Actually, a slightly stronger assumption is needed, namely, the separation between $E$ and $SIZE(2^{\varepsilon \cdot n})$ should hold for almost all input lengths - thanks to Ryan O'Donnel for pointing it out.)</p>

<p>More generally, this paper gives a direct optimal translation of any circuit lower bound into a corresponding derandomization result:
<a href="http://users.cms.caltech.edu/~umans/papers/SU01-final.pdf" rel="nofollow noreferrer">http://users.cms.caltech.edu/~umans/papers/SU01-final.pdf</a></p>

CC BY-SA 3.0
2017-12-07T23:10:27.823Z
just for the record $P/poly$ is much smaller than $SIZE(2^{\epsilon\cdot n})$. right?
Turbo
CC BY-SA 3.0
2017-12-07T23:13:38.947Z
which section are you talking in paper?
Turbo
CC BY-SA 3.0
2017-12-08T01:35:26.807Z
P/poly is indeed much smaller. Regarding the paper, see the last paragraph of Page 4 for the result, and Section 5.4 for the proof (but this proof really depends on more-or-less everything that comes before it).
Or Meir
CC BY-SA 3.0
2017-12-12T00:26:37.280Z
I believe the assumption only shows that BPP is in io-P. For BPP to equal P, E should fail to have 2^(eps n)-size circuits for almost all n.
Ryan O'Donnell
CC BY-SA 3.0
2017-12-12T18:08:42.797Z
You are right of course. I fixed the answer. Thanks!
Or Meir
CC BY-SA 3.0
2017-12-07T22:37:34.227Z
2017-12-12T18:08:05.863Z
2017-12-12T18:08:05.863Z
Or Meir
<p>We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon&gt;0$.</p>

<p>This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon&gt;0$.</p>

<p>Is there any consequence of a stronger derandomization?</p>

<p>Let $a(n)$ be any time constructible superpolynomial.</p>

<ol>
<li><p>What does $NTIME(a(n))\not\subseteq P/poly$ give?</p></li>
<li><p>What does $DTIME(a(n))\not\subseteq P/poly$ give?</p></li>
</ol>

<p>Do these give $BPP\subseteq io-DTIME(poly(n))$ or some thing weaker?</p>

<circuit-complexity><lower-bounds><derandomization><nondeterminism><advice-and-nonuniformity>
What do stronger circuit lower bounds give in terms of derandomization?
Turbo
# What do stronger circuit lower bounds give in terms of derandomization?

(Asked by: username_0 on 2017-12-06)

We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.

This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.

Is there any consequence of a stronger derandomization?

Let $a(n)$ be any time constructible superpolynomial.

1. What does $NTIME(a(n))\not\subseteq P/poly$ give?
2. What does $DTIME(a(n))\not\subseteq P/poly$ give?

Do these give $BPP\subseteq io-DTIME(poly(n))$ or some thing weaker?

**Tags:** circuit-complexity, lower-bounds, derandomization, nondeterminism, advice-and-nonuniformity

---

## 1 answers

### Answer by username_1 on 2017-12-07. Score: 3 | Accepted answer

It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$ then $BPP = P$ (<https://dl.acm.org/citation.cfm?id=258590>).

(Actually, a slightly stronger assumption is needed, namely, the separation between $E$ and $SIZE(2^{\varepsilon \cdot n})$ should hold for almost all input lengths - thanks to Ryan O'Donnel for pointing it out.)

More generally, this paper gives a direct optimal translation of any circuit lower bound into a corresponding derandomization result:
<http://users.cms.caltech.edu/~umans/papers/SU01-final.pdf>

> **Comments:**
> **username_0**: just for the record $P/poly$ is much smaller than $SIZE(2^{\epsilon\cdot n})$. right?  
> **username_0**: which section are you talking in paper?  
> **username_1**: P/poly is indeed much smaller. Regarding the paper, see the last paragraph of Page 4 for the result, and Section 5.4 for the proof (but this proof really depends on more-or-less everything that comes before it).  
> **username_2**: I believe the assumption only shows that BPP is in io-P. For BPP to equal P, E should fail to have 2^(eps n)-size circuits for almost all n.  
> **username_1**: You are right of course. I fixed the answer. Thanks!  

---

