After a briefing on an innovative new theory about information transmission, Juris Hartmanis was ignited with inspiration.
A research mathematician at GE Labs in the early 1960s, Hartmanis saw a correlation with his own work.
“I remember wondering, ‘Could there be a quantitative theory of computation?’”
The answer was yes.
Hartmanis grew up in Latvia, partially under Soviet and German occupation. (His father, a senior Latvian army officer, was arrested by the Soviets and died in prison while Hartmanis was a child.) He finished high school in Germany and earned a degree in physics at the University of Marsburg before coming to America to study mathematics at the University of Kansas and then Caltech.
“Caltech, in their wisdom, decided that I looked more like an applied mathematician than a physicist,” Hartmanis laughs.
Following stints teaching at Cornell and Ohio State University, Hartmanis joined the venerated GE Labs in Schenectady, New York. Together with Richard Stearns, he studied computation, focusing on Turing machines.
The lecture on noise reduction gave Hartmanis an idea: Could they mathematically quantify the efficiency of computing?
“Take the traveling salesman,” he says, citing a classic mathematical problem: A salesman must crisscross the country to make calls to a number of cities. Which route will be the most efficient?
“The problem is good for a computer because it requires mathematical brute force. You must measure all of the possible routes and compare the results to find the answer.”
Hartmanis and Stearns wanted to know if they could proactively quantify how much time such a problem would take to compute.
The result was a seminal paper on computational complexity, published in 1965. In it, Hartmanis and Stearns introduced the time-hierarchy theorem, codifying exactly how a machine, given more time, could solve more problems and defined classes of computational complexity.
Hartmanis and Stearns work ultimately earned them a Turing award in 1993 for helping establish computer science as a formal discipline distinct from mathematics, physics, and electrical engineering. Hartmanis eventually returned to Cornell, where he continued his work and co-founded the university’s computer science department.
Today, he confesses that one of the most satisfying aspects of his work has been to see others build upon it — including researchers at Caltech.
“The outsized impact that Caltech continues to have on the sciences is remarkable,” he says. “I remain in awe of the brilliant minds assembled here.”