We give a simplified, self-contained proof of OpenAI's parity lower bound for constant-depth quantum circuits with arbitrary one-qubit gates, unbounded-arity Toffoli gates, and polynomially many ancillas. The proof establishes product-projection localization and uses it to bound the parity Fourier coefficient of the acceptance probability. We remove one circuit layer directly, ... more >>>

We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a ... more >>>

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