### Juris Hartmanis

Prof. Dr. Juris Hartmanis, * 5 July 1928 in Riga (Latvia)

Turing Award (1993) “with Richard E. Stearns, in recognition of their seminal paper which established the foundations for the field of computational complexity theory”

Juris Hartmanis comes from a prominent Latvian family, his father was the Chief of Staff of the Latvian Army who was arrested during the first Soviet occupation of Latvia in in1940 and later executed in Moscow. Fearing a second Soviet occupation, in late 1944 the family fled by sea to Danzig and with a friends help settled in Marburg.

Juris Hartmanis studied physics in Marburg (Cand. Phil., 1949). The family then emigrated to the US with the help of friends, settling in Kansas City, Missouri. Since at that time, the University of Kansas City did not offer master studies in Physics, Hartmanis chose Mathematics (M.A. 1951). Afterwards he did a doctorate in Mathematics at the California Institute of Technology (Ph.D. 1955) with a thesis about lattice theory, and worked as a lecturer at Cornell University (1955-1957) and as an Assistant Professor at the Ohio State University (1957-1958). He then moved to the General Electric Research Laboratory (1958-1965), and in 1965 became Professor and first Chairman of the newly created Department of Computer Science at Cornell University.

Hartmanis is a member of numerous scientific academies and he holds the Grand Medal of the Latvian Academy of Sciences (Lielo Medalu) (2001).

Juris Hartmanis is married to an interior designer and has three children and four grand children.

How complicated is it to sort a set of numbers, to solve a knot or a Sudoku puzzle? These questions are still unanswered in computer science and mathematics. However, we do have algorithms – computer programs in principle – which solve these complex problems, and take a certain length of time to do so. But what is ‘a certain length of time’? And what does ‘complex’ mean? The work of Juris Hartmanis and Richard E. Stearns addresses exactly these questions. In 1965 they proposed a way to estimate the complexity of a problem by the speed of the algorithm that solves it. To measure speed they used a concept introduced by the British mathematician Alan Turing in 1936: the Turing machine, a formalism to describe computer algorithms in a standard way. Hartmanis and Stearns studied the number of computations an algorithm would need on a Turing machine. Since it is faster to sort 10 numbers than 20, one can study how fast this rate of speed grows with the size of the instance of the problem and can therefore classify algorithms. However, Hartmanis and Stearn soon realized that there are other relevant aspects beside the number of calculations, for instance the size of memory needed by the algorithm and they extended their model accordingly. Their work was therefore the starting point for classifying algorithms into complexity classes which is a vital part of computer science today.

Juris Hartmanis loves science, particularly physics besides computer science, and he enjoys history and biographies. He loves skiing, tennis and small boat sailing.