Juris Hartmanis

Juris Hartmanis (July 5, 1928 - July 29, 2022) was a prominent 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".

Life and career

Hartmanis was born in Latvia. He was a son of Mārtiņš Hartmanis [lv], a general in the Latvian Army, and 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. At the end of World War II, the wife and children of Mārtiņš Hartmanis left Latvia 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 he received a master's degree in applied mathematics at the University of Kansas City (now known as the University of Missouri–Kansas City) in 1951 and a Ph.D. in mathematics from Cal Tech under the supervision of Robert P. Dilworth in 1955. The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999.

After teaching 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. At Cornell, he was one of the founders and the first chairman of its computer science department (which was one of the first computer science departments in the world).

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. Hartmanis is a Fellow of the Association for Computing Machinery and of the American Mathematical Society. Also, a member of the National Academy of Sciences.

Hartmanis died on July 29, 2022. He is survived by his his three children Reneta, Martin, and Audrey.

He is best known for his Turing-award-winning paper with Richard Stearns, in which he introduced time complexity classes TIME(f(n)) and proved the time hierarchy theorem. Another paper by Hartmanis from 1977, with Leonard Berman, introduced the still-unsolved Berman–Hartmanis conjecture that all NP-complete languages are polynomial-time isomorphic.

Awards

• Fellow, American Association for the Advancement of Science (AAAS), 1981
• Member, National Academy of Engineering, 1989
• Member (foreign): Latvian Academy of Sciences, 1990
• Member, American Academy of Arts and Sciences, 1992
• ACM Turing Award 1993
• Charter Fellow, ACM, 1994
• Honorary Doctor of Humane Letters, 1999
• Computing Research Association (CRA) Distinguished Service Award, 2000
• ACM Distinguished Service Award, 2013
• Inaugural Fellow, American Mathematical Society, 2013

Selected publications

• Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets" (PDF), SIAM Journal on Computing, 6 (2): 305–322, doi:10.1137/0206023, hdl:1813/7101, MR 0455536.
• Hartmanis, J.; Stearns, R. E. (1965), "On the computational complexity of algorithms", Transactions of the American Mathematical Society, 117: 285–306, doi:10.2307/1994208, JSTOR 1994208, MR 0170805.