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 ... more >>>

We prove that Parity requires $2^{n^{\Omega(1)}}$ size De Morgan circuits of constant depth using a new method which is completely “top-down” in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds ... more >>>

We address the following fundamental question: is there an efficient deterministic algorithm that, given $1^n$, outputs a string of length $n$ that has polynomial-time bounded Kolmogorov complexity $\tilde{\Omega}(n)$ or even $n - o(n)$?

Under plausible complexity-theoretic assumptions, stating for example that there is an $\epsilon > 0$ for which $TIME[T(n)] ... more >>>

In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... more >>>

In a pair of recent breakthroughs \cite{CHR,Li} it was shown that the classes $S_2^E, ZPE^{NP}$, and $\Sigma_2^E$ require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given ... more >>>

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of ``incompressible strings,'' i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the ``compression problem,'' where we are given ... more >>>