LAUSR

faculty as the Walter R. Read Professor of Computer Science and Engineering, Emeritus. In April 1990, he became chair of a newly created National Research Council committee with the mission of assessing “the scope and direction of computer science and technology.” The result was the 1992 National Academies report Computing the Future: A Broader Agenda for Computer Science and Engineering. That influential 288page report evaluated the U.S. government’s support for Computer Science and Engineering research—support that many felt was inadequate and jeopardized not only U.S. leadership but the very future of computing. Herbert Lin, who co-edited the report with Hartmanis, had recently joined the National Academies Computer Science and Telecommunications Board as a staff officer. “Juris was the first real computer scientist with whom I ever had a close working relationship,” recalls Lin. “Collaborating with him on Computing the Future, he was open to learning about the realities of U.S. science policy, and he was patient with me as he introduced me to the culture of computer science. He didn’t have to treat me as a peer—but he did (and spawned a decades-long relationship). I will always be grateful that our paths crossed for so long and so fortuitously.” In another S&T leadership role, Hartmanis served as assistant director of the National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) from 1996 to 1998. Hartmanis became a Fellow of the American Association for the Advancement of Science in 1981, of the American Academy of Arts and Sciences in 1992, an ACM Fellow in 1994, and a National Academy of Engineering member in 1989. He was also a Fellow of the American Mathematical Society and a National Academy of Sciences memT OD AY THE B ASIC concepts of complexity theory are firmly ensconced in the bedrock of computer science, but that wasn’t always the case. As late as 1965, computer scientists knew that some problems—such as finding an optimal schedule for airlines—seemed much more difficult than other problems: searching for a person’s name in a sorted phonebook, for example. Computing professionals lacked the concepts to discuss these issues rigorously. They didn’t even have the vocabulary. That changed in 1965 when Juris Hartmanis and Richard E. Stearns published their groundbreaking paper “On the Computational Complexity of Algorithms.” That article introduced the concept of a complexity class, providing a straightforward way to reason about complexity using multitape Turing machines, and mathematically proved that there are an infinite number of complexity classes. The paper set the stage for the discovery of space complexity later that year by the same authors, and of the NP-complete complexity class in 1971, independently by Stephen Cook and Leonid Levin. For this work, Hartmanis and Stearns were awarded the 1993 ACM A.M. Turing Award “in recognition of their seminal paper which established the foundations for the field of computational complexity theory.” ACM Fellow Juris Hartmanis died on July 29, 2022, at 94. In addition to being the co-inventor of complexity theory, he was the founding chair of the Cornell Computer Science Department in 1965—one of the first in the world—where he mentored generations of students and faculty members in the emerging field. Indeed, the numerous tributes and personal testaments to Hartmanis that appeared shortly after his death make it clear that he will be remembered as much for his teaching, friendship, and leadership of the computer science community as for his awardwinning brilliance. “I’m immensely grateful to have known him,” wrote MIT professor Ryan Williams in a public memorial. Williams first met Hartmanis when he was an undergraduate at Cornell in 1999. Williams had struggled in his introduction to computing theory course, then took Hartmanis’ graduate complexity course, during which all theory concepts snapped into place. But what really made the difference, Williams wrote, was the mentoring. “Without his faith, I’d have never become a theoretical computer scientist. Without his initial influence, I’d have never been a good one.” Hartmanis would serve as chair of Cornell’s CS department two other times (1977–1983 and 1992–1993). He retired in 2001 but remained on Juris Hartmanis 1928–2022 In Memoriam | DOI:10.1145/3559705 Simson Garfinkel and Eugene H. Spafford