Juris Hartmanis

Last updated

Juris Hartmanis
Juris Hartmanis(2002).jpg
Born(1928-07-05)July 5, 1928
Riga, Latvia
DiedJuly 29, 2022(2022-07-29) (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 (1977)
Neil Immerman (1980)
Jin-Yi Cai (1986) [1]

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

Contents

Life and career

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

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. [8] The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999. [9] 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. [15] 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). [16]

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, [17] 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) [18] 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, [19] also a member of the National Academy of Sciences. [20] He was also a foreign member of the Latvian Academy of Sciences, [21] which bestowed him their Grand Medal  [ lv ] in 2001 for his contributions to computer science. [22]

Hartmanis died on July 29, 2022. [23] [24]

Computational complexity: foundational contributions

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." [25] Their paper [13] 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. 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." [26]

With P.M. Lewis II, Hartmanis and Stearns also defined complexity classes based on space usage and proved the first space hierarchy theorem. [12] In the same year they also proved [27] 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 [28] and conjectured that this holds for all NP-complete sets. [29] Although the conjecture itself remains open, it has led to a large body of research on the structure of NP-complete sets, culminating in Mahaney's theorem on the nonexistence of sparse NP-complete sets. [30] [31] [32] [33] He and his coauthors also defined the Boolean hierarchy. [34] [35]

Hartmanis's 1981 article [14] gives a personal account of developments in this area and in automata theory and discusses the underlying beliefs and philosophy that guided his research. The book written in honor of his 60th birthday, [36] in particular, the chapter by Stearns, [37] is a valuable resource on computational complexity.

In the late 1980's, Hartmanis's exposition [38] on a newly discovered letter dated 20 March 1956 from Gödel to von Neumann brought fresh insight into the early history of computational complexity before his landmark paper with Stearns, touching on interactions among Turing, Gödel, Church, Post, and Kleene. Gödel, in this letter, was the first to question whether a problem equivalent to an NP-complete problem could be solved in quadratic or linear time, presaging the P = NP? question.

Awards

Selected publications

Books
Selected articles

Interviews

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

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.

Theory of computation Academic subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

Stephen Cook American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook, is an American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity. He is a university professor at the University of Toronto, Department of Computer Science and Department of Mathematics.

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time.

Richard M. Karp American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

Richard E. Stearns American computer scientist

Richard Edwin Stearns is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory". In 1994 he was inducted as a Fellow of the Association for Computing Machinery.

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

Shafi Goldwasser American computer scientist

Shafrira Goldwasser is an Israeli-American computer scientist and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at MIT, a professor of mathematical sciences at the Weizmann Institute of Science, Israel, co-founder and chief scientist of Duality Technologies and the director of the Simons Institute for the Theory of Computing in Berkeley, CA.

Johan Torkel Håstad is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes. He has been a professor in theoretical computer science at KTH Royal Institute of Technology in Stockholm, Sweden since 1988, becoming a full professor in 1992. He is a member of the Royal Swedish Academy of Sciences since 2001.

Neil Immerman American theoretical computer scientist

Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst. He is one of the key developers of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory.

Leslie Valiant

Leslie Gabriel Valiant is a British American computer scientist and computational theorist. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. Valiant was awarded the Turing Award in 2010, having been described by the A.C.M. as a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science; in particular for his "striking combination of depth and breadth".

Aleksandr Aleksandrovich Razborov, sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.

In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.

Structural complexity theory

In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.

Rod Downey

Rodney Graham Downey is a New Zealand and Australian mathematician and computer scientist, a professor in the School of Mathematics and Statistics at Victoria University of Wellington in New Zealand. He is known for his work in mathematical logic and computational complexity theory, and in particular for founding the field of parameterised complexity together with Michael Fellows.

In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms.

References

  1. "Juris Hartmanis". mathgenealogy.org. Mathematics Genealogy Project . Retrieved August 4, 2022.
  2. Selman, Alan L., ed. (1990). Complexity Theory Retrospective : In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988. New York, NY: Springer New York. doi:10.1007/978-1-4612-4478-3. ISBN   978-1-4612-4478-3. S2CID   31789744 . Retrieved August 4, 2022.
  3. 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.
  4. 1 2 Hartmanis, Juris (July 26, 2009). "Dr. Juris Hartmanis Interview" (text). Interviewed by William Aspray. Ithaca, New York: ACM Oral History interviews. doi:10.1145/1141880.1775727.
  5. 1 2 Hartmanis, Juris (May 17, 2018). "Juris Hartmanis, 1993 ACM Turing Award Recipient" (video). Interviewed by David Gries. Ithaca, New York: ACM.
  6. In two of the interviews [4] [5] cited in section #Interviews, Hartmanis talks in detail of this period of his life, in which his father was given an estate, Lestene; the Russians occupied Latvia, took his father away, and confiscated Lestene; the Germans took over once more and restored part of Lestene to his family; and the family left Latvia for Germany before the Russians invaded Latvia again.
  7. "A Tribute to Astrid Ivask: A Literary Light". World Literature Today. April 2, 2015. Retrieved August 4, 2022.
  8. Hartmanis, Juris (1955). Some embedding theorems for lattices (PhD thesis). Cal Tech. doi:10.7907/40KS-0T27.
  9. 1 2 "University of Missouri Honorary Degrees". University of Missouri.
  10. 1 2 ; Stearns, R.E. (November 11, 1964). Computational complexity of recursive sequences. 5th Ann. Symp. on Switching Circuit Theory and Logical Design. Princeton, New Jersey: IEEE. pp. 82–90. doi:10.1109/SWCT.1964.6.
  11. 1 2 ; Lewis, P.M.; Stearns, R.E. (May 24, 1963). Wayne A. Kalenich (ed.). Classifications of computations by time and memory requirements. Proc. IFIP Congress 65. New York City: Spartan Books, Inc., Washington, D.C. pp. 31–35. doi:10.2307/2272795. JSTOR   2272795.
  12. 1 2 3 ; Lewis, P.M.; Stearns, R.E. (October 6, 1965). Hierarchies of memory limited computations. FOCS 65: Proc. Sixth Ann. Symp Switching Circuit Theory and Logical Design. New York: IEEE. pp. 179–190. doi:10.1109/FOCS.1965.11.
  13. 1 2 3 ; Stearns, R. E. (1965), "On the computational complexity of algorithms", Transactions of the AMS , 117: 285–306, doi: 10.2307/1994208 , JSTOR   1994208, MR   0170805
  14. 1 2 3 (1981), "Observations about the development of theoretical computer science", IEEE Annals of the History of Computing , 3 (1): 42–51, doi:10.1109/MAHC.1981.10005, hdl: 1813/6244 , ISSN   1058-6180
  15. These early papers developed many principles of computational complexity theory. [10] [11] [12] [13] Hartmanis's 1981 survey paper provides extensive information on the work in computational complexity theory. [14]
  16. Purdue University created the first CS Department in 1962 "History of the Department". Cornell started its CS Department in 1965, "CS Dept. timeline". as did Stanford, "CS Dept. timeline"., Carnegie Mellon, "CS Dept. history". and a few others.
  17. Hartmanis, Juris; Lin, Herbert, eds. (1992). Computing the Future: A broader agenda for computer science and engineering. Washington, DC: National Academies Press. p. 288. doi:10.17226/1982. ISBN   978-0-309-04740-1.
  18. "Juris Hartmanis to Lead NSF's Directorate for CISE". NSF. September 5, 1996. Retrieved August 2, 2022.
  19. 1 2 List of Fellows of the American Mathematical Society, retrieved January 19, 2013.
  20. National Academy of Sciences Members and Foreign Associates Elected Archived May 27, 2013, at the Wayback Machine , National Academy of Sciences, April 30, 2013.
  21. 1 2 "Foreign members". Latvian Academy of Sciences. 1990. Retrieved July 30, 2022.
  22. 1 2 "Lielā medaļa" [Grand Medal]. www.lza.lv (in Latvian). Latvian Academy of Sciences. Archived from the original on January 6, 2022. Retrieved August 4, 2022. 2001 ... Juris Hartmanis, par izcilu ieguldījumu datorzinātņu attīstībā. [2001 ... Juris Hartmanis, for his outstanding contribution to the development of computer science.]
  23. 新智元 [Xin Zhi Yuan] (July 31, 2022). "图灵奖得主,"计算复杂性"理论奠基人Juris Hartmanis逝世,享年94岁" [Turing Award winner and founder of "computational complexity" theory, Juris Hartmanis, dies at 94]. 新浪 finance.sina.com.cn (in Simplified Chinese). Retrieved August 4, 2022.
  24. Waldron, Patricia (August 4, 2022). "Juris Hartmanis, first CS department chair, dies at 94". Cornell Chronicle. Retrieved August 5, 2022.
  25. 1 2 "Turing Award". ACM. 1993. Retrieved July 30, 2022.
  26. See page 103 of his lecture: Karp, Richard M. (February 1986). "Combinatorics, complexity, and randomness". Communications of the ACM . 29 (2): 98–109. doi: 10.1145/5657.5658 . ISSN   0001-0782.
  27. 1 2 Lewis, P.M.; Stearns, R.E.; (October 6, 1965). Memory bounds for recognition of context-free and context-sensitive languages. FOCS 65: Proc. Sixth Ann. Symp Switching Circuit Theory and Logical Design. Ann Arbor, Michigan: IEEE. pp. 191–202. doi:10.1109/FOCS.1965.14.
  28. 1 2 Berman, L.; (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
  29. Berman–Hartmanis conjecture
  30. Mahaney, Stephen R. (October 1982). "Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis". Journal of Computer and System Sciences. 25 (2): 130–143. doi:10.1016/0022-0000(82)90002-2. hdl: 1813/6257 .
  31. Cai, Jin-Yi; Sivakumar, D. (April 1999), "Sparse hard sets for P: resolution of a conjecture of Hartmanis", Journal of Computer and System Sciences , 58 (2): 280–296, doi:10.1006/jcss.1998.1615
  32. Sparse language
  33. Mahaney's theorem
  34. Cai, Jin-Yi; Gundermann, Thomas; ; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd (December 1988), "The boolean hierarchy I: Structural properties", SIAM Journal on Computing , 17 (6): 1232–1252, doi: 10.1137/0217078
  35. Cai, Jin-Yi; Gundermann, Thomas; ; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd (February 1989), "The boolean hierarchy II: Applications", SIAM Journal on Computing , 18 (1): 95–111, doi:10.1137/0218007
  36. Selman, Alan L., ed. (1990). Complexity Theory Retrospective. Springer New York, NY. doi:10.1007/978-1-4612-4478-3. ISBN   978-1-4612-8793-3.
  37. Stearns, R. E. (1990). "Juris Hartmanis: The beginnings of computational complexity". In Selman, Alan L. (ed.). Complexity Theory Retrospective. Springer New York, NY. doi:10.1007/978-1-4612-4478-3. ISBN   978-1-4612-8793-3.
  38. 1 2 Hartmanis, Juris (1989). "Gödel, von Neumann, and the P =? NP problem". Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.
  39. "Fellows". American Association for the Advancement of Science. 1981. Retrieved July 30, 2022.
  40. "NAE Website – Dr. Juris Hartmanis". National Academy of Engineering.
  41. "Members". American Academy of Arts and Sciences. 1992. Retrieved July 30, 2022.
  42. "Alexander von Humboldt Foundation, Juris Hartmanis". Alexander von Humboldt Foundation . 1993.
  43. "ACM Fellows". ACM. 1994. Retrieved July 30, 2022.
  44. "Juris Hartmanis: ACM Fellow". 1994. Retrieved July 9, 2022.
  45. "Distinguished Service Award". Computing Research Association. CRA. January 16, 2015. Retrieved July 30, 2022.
  46. "ACM Distinguished Service Award". ACM. 2013. Retrieved July 30, 2022.
  47. "Juris Hartmanis: Distinguished Service Award". 2013. Retrieved July 30, 2022.
  48. "Member Emeritus". National Academy of Sciences (NAS) . Retrieved July 31, 2022.
  49. ; Richard E., Stearns (1966). Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N.J.: Prentice-Hall. p. 211. ISBN   0130222771.
  50. (1978). Feasible Computations and Provable Complexity Properties. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). p. 62. ISBN   978-0-898710-27-4.
  51. , ed. (1989). Computational Complexity Theory. AMS. p. 128. ISBN   978-0-8218-0131-4.
  52. ; Lin, Herbert, eds. (1992). Computing the Future: A broader agenda for computer science and engineering. Washington, DC: The National Academies Press. p. 288. doi:10.17226/1982. ISBN   978-0-309-04740-1.
  53. Hartmanis, Juris (March 31, 2010). "A Conversation with Juris Hartmanis" (video). Interviewed by David Gries. Ithaca, New York: Internet-First University Press.
  54. Shustek, Len (2015). "An interview with Juris Hartmanis". CACM . 58 (4): 33–37. doi:10.1145/2736346. S2CID   35051248.