Juris Hartmanis, a Turing Award-winning pioneer who was instrumental in establishing computer science as an independent field, and founding chair of Cornell’s Department of Computer Science, died July 29 at 94.
Often called "the father of computational complexity," Hartmanis discovered a set of fundamental laws that govern the difficulty of computation, laying the foundation for a comprehensive theory of the efficiency and limits of computing.
At Cornell, Hartmanis built one of the first computer science departments in the world. His colleagues credit his vision and leadership for cultivating one of the leading computer science departments in the U.S.
“Juris was a visionary researcher, leader, and mentor,” said Kavita Bala, dean of the Cornell Ann S. Bowers College of Computing and Information Science. “His legacy lives on in the discipline he helped build and in the minds of the many people, like me, he inspired."
Hartmanis was born in Riga, Latvia in 1928. His father, a general in the Latvian army, died in prison after the Soviet occupation of Latvia in the 1940s, leading Hartmanis and his family to emigrate to Germany. He completed high school in a displaced persons camp and earned an undergraduate degree in physics from the University of Marburg. Through the sponsorship of a family friend, he moved to the U.S. and received his master’s degree in mathematics at the University of Kansas City (now known as the University of Missouri–Kansas City) in 1951 and his Ph.D. in mathematics from the California Institute of Technology in 1955.
From 1955 to 1957 he was an instructor in mathematics at Cornell, followed by nine months as an assistant professor of mathematics at Ohio State University. In 1958 he was tempted by industrial research and joined General Electric (GE) Research Laboratory in Schenectady, New York, where he spent the next seven years.
It was at GE that he and colleague Richard Stearns founded the field of computational complexity, an area of research that remains one of the central topics in computer science to this day. There had been earlier work in analysis of algorithms that attempted to establish upper or lower time bounds on specific algorithms for various computational problems, but very few general principles that unified the behavior of these algorithms.
Their key contribution was to study the inherent complexity of the problems themselves. In their 1965 paper, “On the Computational Complexity of Algorithms,” they defined the fundamental notion of a complexity class — a class of problems that are solvable within a certain time bound on a multitape Turing machine. They showed that this notion is extremely robust in the sense that complexity classes are independent of time scale and impervious to minor modifications of the machine model, thus the results were relevant to any reasonable model of computation. They proved several theorems regarding separation and containment of complexity classes, thereby establishing the existence of an infinite hierarchy of complexity classes.
For this foundational work, Hartmanis and Stearns received the 1993 Turing Award – the premier honor in computer science.
In 1965, Hartmanis returned to Cornell as the first chair of the newly founded Department of Computer Science. Under his leadership, graduates went on to become faculty members at new computer science departments forming all over the country.
“Juris has been an inspiration to generations of computer scientists since the early days of the field,” said Dexter Kozen, the Joseph Newton Pew Jr. Professor in Engineering in the Department of Computer Science. “I am fortunate to have studied under Juris at Cornell, where his influence on the culture of the department is still felt to this day. The news of his passing has left me with a profound sense of loss, as I’m sure is true with many.”
Hartmanis served as chair of the department three times — 1965–71, 1977–83, and 1992–93 — and ultimately retired from the university in 2001 as the Walter R. Read Professor of Computer Science and Engineering Emeritus.
"We have so much to thank Juris for,” said Éva Tardos, the Jacob Gould Schurman Professor of Computer Science and chair of the Department of Computer Science. “He founded our department, and established the collegial and collaborative culture that has been helping us be a great department to this day."
Beyond his service to Cornell, Hartmanis contributed to national efforts to advance the field of computer science. He chaired a National Research Council Study that yielded the 1992 publication, “Computing the Future: A Broader Agenda for Computer Science and Engineering.” The report laid out a research agenda and recommended a framework of education, funding, and leadership designed to bring computing into the 21st century.
From 1996 to 1998, Hartmanis served as the assistant director of the National Science Foundation, where he led the Directorate of Computer and Information Science and Engineering (CISE). There, he steered the efforts to transform the academic research network NSFnet into the early Internet.
He also served on the science board and science steering committee of the Santa Fe Institute, an independent, nonprofit research group founded to advance research in complexity science.
Among his many awards, Hartmanis was a member of the American Academy of Arts and Sciences, the National Academy of Engineering, the National Academy of Sciences, and the Latvian Academy of Sciences, and a fellow of the Association for Computing Machinery and the American Mathematical Society. He received the Bolzano Gold Medal from the Academy of Sciences in the Czech Republic and the Computing Research Association’s Distinguished Service Award. In 1993, he was the recipient of a Humboldt Foundation Senior U.S. Scientist Award, and he held honorary doctorates from the University of Missouri and the University of Dortmund.
Juris was predeceased by his wife Elly (Rehwaldt) and is survived by three children, Reneta McCarthy, Martin Hartmanis, and Audrey Langkammerer.
The family requests that in lieu of flowers, donations can be sent to the Ithaca Sciencenter in his memory. A Celebration of Life of Juris Hartmanis will take place at the Ithaca Yacht Club on Aug. 15 from noon to 2 p.m.
By Patricia Waldron, a science writer for the Cornell Ann S. Bowers College of Computing and Information Science.