We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $\lambda(n) = n^{-\omega(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $1/2+\lambda(n)$ with success probability at least $1-1/n^k$. ... more >>>

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 >>>