We investigate central questions in complexity theory through the lens of time-bounded Kolmogorov complexity, focusing on $\textit{nondeterministic}$ measures [AKRR03] and their extensions. In more detail, we consider succinct encodings of a string by programs that may be nondeterministic (nK), randomized (rK), or combine both resources – yielding richer notions such ... more >>>

The classical coding theorem in Kolmogorov complexity [Lev74] states that if a string $x$ is sampled with probability $\geq \delta$ by an algorithm with prefix-free domain, then $K(x) \leq \log(1/\delta) + O(1)$. Motivated by applications in algorithms, average-case complexity, learning, and cryptography, computationally efficient variants of this result have been ... 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 >>>