Juris Hartmanis

Juris Hartmanis (born July 5, 1928) is 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".

Juris Hartmanis
Born (1928-07-05) July 5, 1928
Alma mater
AwardsTuring Award (1993)
Scientific career
FieldsComputer Science
Institutions
Doctoral studentsAllan Borodin
Dexter Kozen

Hartmanis was born in Latvia. He was a son of Mārtiņš Hartmanis,[1] a general in the Latvian Army, and brother of poet Astrid Ivask. After the Soviet Union occupied Latvia in 1940, Mārtiņš Hartmanis was arrested by 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. Then he moved to the United States, where he received 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 Caltech under the supervision of Robert P. Dilworth in 1955. The University of Missouri-Kansas City honored him with 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 founders and the first chairman of its computer science department (which was one of the first computer science departments in the world). Hartmanis is a Fellow of the Association for Computing Machinery and of the American Mathematical Society[2] and a member of the National Academy of Engineering and National Academy of Sciences.[3]

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.

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.
gollark: I decided to look at the code in more detail. This was a mistake. It contained thousands of lines with minimally useful comments, for some reason its own implementation of hash tables (this is very C, I suppose), and apparently its own implementation of WiFi mesh things even though that should really be handled generically for any device.
gollark: After I was able to work through git's terrible CLI enough to make that work, and "fixed" some merge conflicts, it somehow compiled still, but upon plugging in the thing, hung things again. I had dmesg open, and apparently it was a page fault somehow in the code assigning names or something?
gollark: Then I noticed that they had merged patches a lot from the repo for a similar wireless chip, so I decided to just try and merge the "kernel 5.10 compatibility" thing from that, which had not made it in yet.
gollark: There was a repo on GitHub for doing that with it, but `insmod`ing it after compiling *somehow* hung my kernel so I had to reboot.
gollark: I mean, possibly. I wanted to get my USB WiFi thing to work in monitor mode for testing for non-evil purposes, but it was just really bad to do so.

References

  1. In the Baltic languages, own-names are not lexical constants but have different grammatical forms. Hartmanis must be understood as Hartman-is, whereby Hartman is the stem of the own-name, whereas the suffix -is indicates a masculine grammatical form in the Latvian language. In a similar manner, for example, the philosopher Kant is known as Kantas in the Lithuanian language.
  2. List of Fellows of the American Mathematical Society, retrieved 2013-01-19.
  3. National Academy of Sciences Members and Foreign Associates Elected Archived 2013-05-27 at the Wayback Machine, National Academy of Sciences, April 30, 2013.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.