Insertion sort is a basic algorithm for sorting permutations: it repeatedly cuts out one element and inserts it at its place among the elements sorted so far.
It sorts every permutation of length $n$ with at most $n-1$ such moves, and some permutations cannot be sorted with fewer ... more >>>

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