Richard Stearns (1936-2026)

Richard Stearns (right) and Juris Hartmanis in May 1963. The main theorem from their seminal paper is on the blackboard. Stearns sent Lance this picture to help celebrate the 50th anniversary of their paper.Richard Stearns died on August 29, 2026. Readers of this blog probably know him from the Hartmanis-Stearns paper On the computational complexity of algorithms which appeared in Transactions of the American Mathematical Society in 1965, and his paper with F. C. Hennie that gave the still tightest known separation for the deterministic time hierarchy.The Hartmanis-Stearns paper first defined DTIME(T(n)) and other classes and named our field and this blog. That paper has been honored in two ways:1) The paper was one of the reasons Hartmanis and Stearns won the Turing Award in 1993.2) Lance Fortnow chose that paper as one of his favorites, see here.--------In this post we discuss a different great paper by Stearns. First some background.Consider the following problems.1) Find a…