On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract

The Exponential-Time Hypothesis (ETH) is a strengthening of the $\mathcal{P}\neq \mathcal{NP}$ conjecture, stating that 3-SAT on $n$ variables cannot be solved in (uniform) time $2^{\epsilon\cdot n}$ , for some $\epsilon > 0$ . In recent years, analogous hypotheses that are “exponentially-strong” forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq \mathcal{BPP}$ or $co\mathcal{NP}\not\subseteq \mathcal{NP}$ ) have also been introduced, and have become widely influential. In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely-related questions of derandomization and circuit lower bounds. We show that even relatively-mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: 1)The Randomized Exponential-Time Hypothesis (rETH) implies that $\mathcal{BPP}$ can be simulated on “average-case” in deterministic (nearly-)polynomial-time (i.e., in time $2^{\tilde{O}(\log(n))}=n^{\log\!\log(n)^{O(1)}}$ ). The derandomization relies on a conditional construction of a pseudorandom generator with near-exponential stretch (i.e., with seed length $\tilde{O}(\log(n)))$ ; this significantly improves the state-of-the-art in uniform “hardness-to-randomness” results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses. 2)The Non-Deterministic Exponential-Time Hypothesis (NETH) implies that derandomization of $\mathcal{BPP}$ is completely equivalent to circuit lower bounds against $\mathcal{E}$ , and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Lastly, we show that disproving certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CireuitSAT for circuits over n bits of size poly(n) can be solved by probabilistic algorithms in time 2n/polylog(n), then $\mathcal{BP}\epsilon$ does not have circuits of quasilinear size.