We continue the study of distribution testing in the Huge Object Model (Goldreich and Ron, 2023), focusing on the flagship question of \emph{parameterized uniformity testing}: given access to data in $\{0,1\}^n$, is its underlying probability distribution uniform on a small subset of size $m$? The focus here is on both ... more >>>

Understanding the average-case complexity of $\mathrm{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathrm{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathrm{PH}$ is easy on average, ... more >>>

Catalytic computation involves the study of Turing machines that are provided an additional catalytic tape (with arbitrary content) that the machine may use while ensuring that the tape contents are restored at the end of the computation. Although it is known that catalytic log-space machines are at least as powerful ... more >>>