# Juris Hartmanis

Juris Hartmanis | |
---|---|

Born | Riga, Latvia | July 5, 1928

Died | July 29, 2022 | (aged 94)

Alma mater | |

Awards | Turing Award (1993) |

Scientific career | |

Fields | Computer science |

Institutions | |

Doctoral advisor | Robert P. Dilworth |

Doctoral students | Allan Borodin (1969), Dexter Kozen (1976), Neil Immerman (1980), Jin-Yi Cai (1986) |

**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".

## Life and career

Hartmanis was born in Latvia on July 5, 1928. He was a son of Mārtiņš HartmanisAstrid 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.

, a general in the Latvian Army, and brother of the poetThey 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 Cal Tech under the supervision of Robert P. Dilworth. The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999. 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. 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. He was assistant director of the National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) from 1996 to 1998.

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. He was also a foreign member of the Latvian Academy of Sciences, which bestowed him their Grand Medal in 2001 for his contributions to computer science.

Along with R.E. Stearns, Hartmanis received the 1993 Turing Award for a paper in which they 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.

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

## 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
- Humboldt Foundation Research Award, 1993
- Charter Fellow, ACM, 1994
- Honorary Doctor of Humane Letters, 1999
- Computing Research Association (CRA) Distinguished Service Award, 2000
- Grand MedalLatvian Academy of Sciences, 2001 of the
- ACM Distinguished Service Award, 2013
- Inaugural Fellow, American Mathematical Society, 2013
- Member, National Academy of Sciences, 2013

## Selected publications

- Books

*Algebraic Structure Theory of Sequential Machines*1966 (with R.E. Stearns)*Feasible Computations and Provable Complexity Properties*1978*Computational Complexity Theory*(ed.) 1989*Computing the Future: A broader agenda for computer science and engineering*(ed.) 1992 (with Herbert Lin)

- Selected articles

- "Computational complexity of recursive sequences" 1964 (with R.E. Stearns)
- "Classifications of computations by time and memory requirements" 1965 (with P.M. Lewis and R.E. Stearns)
- "Hierarchies of memory limited computations" 1965 (with P.M. Lewis and R.E. Stearns)
- "On the computational complexity of algorithms" 1965 (with R.E. Stearns)
- Memory bounds for recognition of context-free and context-sensitive languages 1965 (with P.M. Lewis and R.E. Stearns)
- "On isomorphisms and density of NP and other complete sets" 1977 (with L. Berman)
- "Observations about the development of theoretical computer science" 1981

## Interviews

Juris Hartmanis has been interviewed four times. Videos are available for two of them. The most far-reaching one is by William Aspray.

- William Aspray interviews Hartmanis for the ACM Oral History interviews, 2009
- David Gries interviews Hartmanis for the Cornell ecommons collection, 2010
- Len Shustek interviews Hartmanis in an article in CACM, 2015
- David Gries interviews Hartmanis as ACM Turing Award recipient, 2018

- 1928 births
- 2022 deaths
- 20th-century American engineers
- 20th-century American scientists
- American computer scientists
- Theoretical computer scientists
- Fellows of the Association for Computing Machinery
- Fellows of the American Mathematical Society
- Members of the United States National Academy of Engineering
- Members of the United States National Academy of Sciences
- Turing Award laureates
- Cornell University faculty
- California Institute of Technology alumni
- Latvian emigrants to the United States
- Latvian World War II refugees
- Santa Fe Institute people
- University of Marburg alumni
- University of Kansas alumni
- University of Missouri–Kansas City alumni
- Ohio State University faculty
- Scientists from Riga