# What do stronger circuit lower bounds give in terms of derandomization?

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?

## 1 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

• just for the record $P/poly$ is much smaller than $SIZE(2^{\epsilon\cdot n})$. right? – 1.. Dec 7 '17 at 23:10
• which section are you talking in paper? – 1.. Dec 7 '17 at 23:13
• 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 Dec 8 '17 at 1:35
• 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 Dec 12 '17 at 0:26
• You are right of course. I fixed the answer. Thanks! – Or Meir Dec 12 '17 at 18:08