Turing Award-winner Richard Stearns ’58 celebrated after passing
Stearns majored in mathematics at Carleton and went on to help found computational complexity theory.
Richard “Dick” Edwin Stearns ’58 passed away on August 29, 2026 at the age of 90. He was one of the fathers of computational complexity theory, earning the A.M. Turing Award from the Association for Computing Machinery (ACM) in recognition of his seminal paper with Juris Hartmanis establishing the field’s foundations.
The ACM recognized him this month with an “In Memoriam” piece, writing that Stearns and Hartmanis “wrote the paper at an industrial research laboratory about a field that did not yet have a name. They gave it one.”
In 1960, Stearns was not looking for a summer job, but his closest friend from Carleton College, Roger Kirchner, was. When a General Electric recruiter visited Harvard University, where Kirchner was a graduate student, Kirchner interviewed and told the recruiter, “By the way, you want to hire Dick Stearns as well.” Stearns, then finishing a doctorate at Princeton University, was invited to Schenectady, N.Y., hired for the summer, and joined the General Electric (GE) Research Laboratory permanently in June 1961, while still typing his dissertation.
There he met Juris Hartmanis, who had just published a paper on the state assignment problem: how to encode the internal states of a sequential machine using as few discrete components as possible. Stearns developed a more general approach, built on what he called partition pairs, which led to their first joint publication.
Four Turing laureates have remarked on what [the computational complexity theory] paper did. Said 1982 Turing laureate Stephen Cook, “This paper was widely read and gave the field its title.” Richard Karp, Turing laureate of 1985, said, “[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory.” Said John Hopcroft, who shared the 1986 Turing Award with Robert Tarjan, “Turing’s work might have remained in the realm of mathematics and logic were it not for a seminal paper on the computational complexity of algorithms by mathematicians Hartmanis and Stearns.” 2020 Turing laureate Jeffrey Ullman wrote that the work “rightly and belatedly won the Turing award” and was “both amazingly insightful and widely useful.”
A second thread ran the length of his life. Stearns wrote his first paper, on Arrow’s paradox, as a Carleton College senior; The American Mathematical Monthly published it in 1959. His Princeton dissertation under Harold Kuhn examined three-person cooperative games without side payments; he found a game with no von Neumann-Morgenstern solution. Robert Aumann, then visiting Princeton, mentored him in practice. “Aumann later got the Nobel Prize in Economics,” Stearns observed, “so I can say I was mentored by a Nobel Laureate.” Work he did in the 1960s for the U.S. Arms Control and Disarmament Agency on repeated games with incomplete information became a chapter of Aumann and Maschler’s 1995 book, which won that year’s Lanchester Prize. The title page reads “with the collaboration of Richard E. Stearns”; he called himself “kind of a semi-author,” and the episode “the story of how I almost won the Lanchester Prize.”
He was still working when he died. On August 12, seventeen days before his death, he emailed Jingnan Xie at Millersville University asking for the manuscript of a paper on two-way finite automata with quantum and classical states, so that he could review it. Xie, his co-author on several later papers, described what that review might have entailed: “Even in his final years, Prof. Stearns remained actively engaged with the mathematics. He read proofs carefully, caught subtle issues, and sometimes saw that an argument could support a stronger theorem than we had originally stated,” Xie said. That quantum automata paper is unfinished. Another, on cellular automata, remains under review.
Read the full piece from the ACM.
At Stearns’s request, memorial gifts may be made to Carleton at give.carleton.edu in his name; enter “Richard Stearns Memorial Fund” in the designation section.
Stearns’s full obituary is available on Legacy.com. Carleton community members can leave comments of remembrance and respect on his Carleton Farewells page.