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