We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF).
Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization ... more >>>

We prove that for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses, every $\mathsf{AC}^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p = n^{-1/(2d)}$. The proof follows ... more >>>

We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since ... more >>>