Paper 2026/2728

Tight Depth Lower Bounds for Stretch Amplification

Abstract

We investigate the depth overhead of stretch-amplification for pseudorandom generators in the black-box model. We show that any black box construction of a PRG $H: \{0,1\}^m \to \{0,1\}^M$ which makes $\mathrm{poly}(n)$ queries to a PRG $G: \{0,1\}^n \to \{0,1\}^N$ in $d$ adaptive phases during each evaluation (and with a black-box reduction to the security of $G$) must satisfy: $M \leq (m + O(\log n)) \Bigl( \frac{N}{n - O(\log n)} \Bigr)^d$. This implies that the standard amplification procedure [GM'84, GGM'86] based on repeated composition of $G$ is essentially optimal. In particular, amplifying $n \mapsto n+1$ to $m \mapsto 2m$ requires depth overhead $d = \Omega(\frac{n}{\log n})$, and amplifying $n \mapsto 2n$ to $m \mapsto m^2$ requires depth overhead $d = \Omega(\log n)$; each of these bounds is tight up to a constant factor. As an immediate corollary we obtain tight lower bounds on the depth complexity of black-box constructions of PRFs from PRGs. Both of these problems (pertaining to amplification and PRF construction) have been studied in various prior works [V'05, MV'11, BJP'11, MV'15, BMM'24, ADV'26]. Despite progress on special cases in which the structure of the reductions is constrained, it was previously unknown whether completely parallel constructions ($d=1$) existed in every stretch regime. The kinds of amplification procedures we investigate have more recently found use outside of cryptography in the study of range avoidance ("Avoid") [K'21]. We show an analogous result in this setting: any black-box $\mathrm{FP^{NP}}$ reduction from an Avoid instance $G: \{0,1\}^n \to \{0,1\}^N$ to a second Avoid instance $H: \{0,1\}^m \to \{0,1\}^M$ which has "depth $d$" in the above sense must satisfy the same bound relating $n,N,m,M,d$. Using this impossibility result for Avoid, we construct an oracle relative to which $\mathrm{E} \not\subseteq \mathrm{NC}/\mathrm{poly}$ but $\mathrm{E^{NP}} \subseteq \mathrm{P}/\mathrm{poly}$. Our oracle separation implies that in the relativized setting, the bounded arithmetic theory $S^1_2$ cannot prove the existence of functions outside $\mathrm{P}/\mathrm{poly}$, even given as an axiom the existence of functions outside $\mathrm{NC}/\mathrm{poly}$.