Turing Award Winner Richard Stearns, Co-Founder of Computational Complexity, Dies at 90
fortnow · x · 2026-09-05
Richard Stearns, pioneer of computational complexity, died on August 29, 2026, at age 90. His 1965 paper with Juris Hartmanis, On the computational complexity of algorithms, first defined DTIME(T(n)) and other classes and named the field, earning both the 1993 Turing Award.
Lance Fortnow's post also highlights a lesser-known gem: Stearns's paper with F. C. Hennie giving the still-tightest known separation for the deterministic time hierarchy. It reviews related automata results — the 2^n NFA→DFA bound, the linear CFG→PDA bound, and the fact that the minimal-DFA-size function for CFG-described regular languages is uncomputable (reductions from HALT, later tightened to INF).
Stearns once sent Fortnow a photo of himself and Hartmanis at a blackboard from May 1963 to mark the blog's anniversary.
More from Research
- MultiMDM: multi-mask diffusion LMs draft before writing for few-step generation — QuanquanGu · 2026-09-05
- Google DeepMind Publishes Free Book on Scaling LLMs Across TPUs and GPUs — goyal__pramod · 2026-09-05
- Prime Super Flash MoE: 1.2x BF16 and 1.6x MXFP8 speedups over upstream on B200 — retr0jirachi · 2026-09-05
- Kevin Buzzard verifies Anthropic's 13.4M-line Lean proof of Fermat's Last Theorem — AlexKontorovich · 2026-09-05
- Prime Intellect cuts GLM-5.2 RL weight transfer from 86s to 4s with NIXL and ModelExpress — samsja19 · 2026-09-05
- Karpathy's 'overfit first, regularize later' still rules large-scale post-training — rdesh26 · 2026-09-05