List recovery of error-correcting codes has emerged as a fundamental notion with broad applications across coding theory and theoretical computer science. Folded Reed-Solomon (FRS) and univariate multiplicity codes are explicit constructions which can be efficiently list-recovered up to capacity, namely a fraction of errors approaching $1-R$ where $R$ is the ... 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 >>>

Range avoidance (Avoid) is the computational problem in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$ and the goal is to find a string $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. Avoid was introduced recently by Kleinberg, Korten, Mitropolsky, and Papadimitriou ... more >>>