We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between $N$ and $2N$), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem ... more >>>

Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of $\mathrm{NP}$ is a central research direction. A longstanding open problem in this area is to establish the $\mathrm{NP}$-hardness of $\mathrm{MINKT}$ [Ko91], the problem of ... more >>>

We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is ``structured" (i.e., $K^t(x) n - \log n$)---characterizes OWF,
but with either of the following caveats (1) considering a non-standard notion of \emph{probabilistic $K^t$}, as opposed to the ... more >>>