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)] \not \subseteq TIME^{NP}[T(n)^{\epsilon}]/2^{\epsilon n}$ for appropriately chosen time-constructible $T$, we show that the answer to this question is positive (answering a question of [RSW22]), and that the Range Avoidance problem [KKMP21, Korten21, RSW22] is efficiently solvable for uniform sequences of circuits with close to minimal stretch (answering a question of [ILW23]).

We obtain our results by giving efficient constructions of pseudo-random generators with almost optimal seed length against algorithms with small advice, under assumptions of the form mentioned above. We also apply our results to give the first complexity-theoretic evidence for explicit constructions of objects such as rigid matrices (in the sense of Valiant) and Ramsey graphs with near-optimal parameters.