This paper presents another step in the research program of tightly relating derandomization and circuit lower bounds; specifically, in the flavor put forward by Ryan Williams' celebrated works.
First, Roei observes that a special case of a result of Murray and Williams (i.e., their Thm 1.2) implies that if prBPP=prP, then NQP does not have poly-size circuits, where NQP is the quasi-polynomial version of NP (i.e., $NQP = NTIME(n^{polylog}$). Next, Roei strengthens this result by using the easy witness lemma of Murray and Williams and presenting a refined version of Williams' strategy. Consequently, he shows that if prBPP=prP, then NTIME(t(n)) does not have poly-size circuits, where $t$ is any nice function that grows faster than any polynomial (e.g., $f(n) = n^{log-star n}$).
Roei's paper provides a good account of Williams' basic strategy, which is accessible to general TOC audience. This, by itself, is a great service to the TOC community. Experts are also accomodated by the paper's organization (see Sections 2 and 5).
Additional Discussion (3-Jan-18): Let $t$ stand for a nice function that grows only mildly faster than any polynomial. Now, the conclusion NTIME(t) is not contained in $P/poly$ is presented as a weak version of NP is not in $P/poly$, but it may as well be viewed as a weak version of DTIME(t) is not in $P/poly$. Indeed, NTIME(t) extends both DTIME(t) and NP, and so both interpretations are legitimate. Furthermore, NTIME(t) is well-known to be stronger than NP, whereas a separation between NTIME(t) and DTIME(t) (or NTIME(t) and DTIME(poly(t))) seems closely related to the conjecture separation of P from NP. On the one hand, the second separation feels more fundamental, and so one may argue that NTIME(t) is not in $P/poly$ is morally closer to NP is not in $P/poly$, but on the other hand one may feel that DTIME(t) is not in $P/poly$ may be easier to establish than NP is not in $P/poly$. (I am intentionally ignoring the controversial question of whether the current conditional proof of NTIME(t) is not in $P/poly$ capitalizes more on the fact that $t$ is super-polynomial or on the non-determinism of the larger class. I believe that an answer to this question only provides circumstantial evidence towards the question of interpretation briefly discussed above.)
We show that any proof that promise-BPP = promise-P necessitates proving circuit lower bounds that ``almost'' yield that P neq NP. More accurately, we show that if promise-BPP = promise-P, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]$ is not contained in $P/poly$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that NP is not contained in $P/poly$) without unconditionally proving that P neq NP.
This paper is a direct follow-up to the very recent breakthrough of Murray and Williams (ECCC, 2017), in which they proved a new ``easy witness lemma'' for $NTIME[o(2^n)]$. Following their approach, we apply the new lemma within the celebrated proof strategy of Williams (SICOMP, 2013), and derive our result by using a parameter setting that is different than the ones they considered.
See ECCC TR18-003.
Additional Comment by Roei (9-Jan-18 following a discussion on 3-Jan-18): A revision that clarifies the meaning of the result will be posted soon.
One may indeed interpret the lower bound "NTIME[n^f(n)] not in P/poly" in two ways. The first is as a predecessor of "NP not in P/poly", as hinted by the title, and the second is as a predecessor of "DTIME[n^f(n)] not in P/poly", as others suggest. Both seem valid to me, and I personally see no convincing reason that extending the lower bound in the latter way will be easier than extending it in the former way. (In particular, note that when trying to prove either statement (i.e., "DTIME[n^f(n)] not in P/poly" or "NP not in P/poly") we have to handle two conflicting resources, which of course doesn't happen with standard time-hierarchy...)
Indeed it will be great to have any indication as to whether it is "easier" to prove such an extended time-hierarchy theorem (for algorithms-vs-circuits) or to prove "NP not in P/poly". Note that, so far, our circuit lower bounds for P/poly tend to crucially rely on non-determinism, and that we have been able to make progress in proving that derandomization implies (small!) NTIME lower bounds, but it's still open whether derandomization implies lower bounds even against EXP.