Juris Hartmanis

Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".

Hartmanis was born in Latvia on July 5, 1928.

He was a son of, a general in the Latvian Army, and Irma Marija Hartmane.

He was the younger brother of the poet Astrid Ivask.

After the Soviet Union occupied Latvia in 1940, Mārtiņš Hartmanis was arrested by the Soviets and died in a prison.

Later in World War II, the wife and children of Mārtiņš Hartmanis left Latvia in 1944 as refugees, fearing for their safety if the Soviet Union took over Latvia again.

They first moved to Germany, where Juris Hartmanis received the equivalent of a master's degree in physics from the University of Marburg.

He then moved to the United States, where in 1951 he received a master's degree in applied mathematics at the University of Kansas City (now known as the University of Missouri–Kansas City) and in 1955 a Ph.D. in mathematics from Caltech under the supervision of Robert P. Dilworth.

After teaching mathematics at Cornell University and Ohio State University, Hartmanis joined the General Electric Research Laboratory in 1958.

While at General Electric, he developed many principles of computational complexity theory.

In 1965, he became a professor at Cornell University.

He was one of the founders and the first chair of its computer science department (which was one of the first computer science departments in the world).

Hartmanis contributed to national efforts to advance computer science and engineering (CS&E) in many ways.

In his own Turing Award lecture, Richard M. Karp remarks that "[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory."

With P.M. Lewis II, Hartmanis and Stearns also defined complexity classes based on space usage and proved

the first space hierarchy theorem.

In the same year they

also proved that every context-free language has deterministic

space complexity

(log n)2

, which contained the essential idea that led

to Savitch's theorem on space complexity.

Hartmanis continued to make significant contributions to the field of computational complexity for decades.

With Leonard Berman, he proved that all natural NP-complete languages are polynomial-time isomorphic and conjectured

that this holds for all NP-complete sets.

In 1989, Hartmanis was elected as a member into the National Academy of Engineering for fundamental contributions to computational complexity theory and to research and education in computing.

He was a Fellow of the Association for Computing Machinery and of the American Mathematical Society, also a member of the National Academy of Sciences.

Most significantly, he chaired the National Research Council study that resulted in the 1992 publication Computing the Future – A Broad Agenda for Computer Science and Engineering, which made recommendations based on its priorities to sustain the core effort in CS&E, to broaden the field, and to improve undergrad education in CS&E.

In 1993, Hartmanis and R.E. Stearns received

the highest prize in computer science, the Turing Award.

The citation reads,

"In recognition of their seminal paper which established the foundations for the field of computational complexity theory."

Their paper

defined the foundational notion of a Complexity class, a way of classifying computational problems according to the time required to solve them.

They went on to prove a number of fundamental results such as the

Time hierarchy theorem.

He was assistant director of the National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) from 1996 to 1998.

The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999.

He was also a foreign member of the Latvian Academy of Sciences, which bestowed him their Grand Medal of the Latvian Academy of Sciences in 2001 for his contributions to computer science.

Hartmanis died on July 29, 2022.