Michael O. Rabin was a major founder and leader of theoretical computer science. He died on April 14, 2026, at the age of 94. This paper aims to survey the wide scope and lasting impact of his research.

more >>>

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