54 ms·

Juris Hartmanis 1928–2022

122 points by sizzle 4y ago

Lapsa 4y ago
name, surname sounds unmistakably Latvian. Turing award... and I didn't even know... rest in peace
- b3kart 4y ago
  Very mild, but also unmistakably Latvian accent. Was also surprised to learn about Juris. RIP indeed.
sireat 4y ago
Juris Hartmanis was Turing award winner laying out foundations for complexity theory. His life in his own words: https://cacm.acm.org/magazines/2015/4/184690-an-interview-wi https://cacm.acm.org/magazines/2015/4/184690-an-interview-wi... "I also discovered, during my education and early research experience, that you do not have to know that much to do research. With a good background education, one can very quickly absorb the necessary specialized knowledge for a specific research area. I think what Caltech really taught me was to be independent, and to try to go to the essence of a problem." In some ways a typical(and tragically sad) beginning for Latvian(and other Baltic) refugees at the end of WW2 but quite extraordinary achievements later on.
082349872349872 4y ago
Also cowrote "Algebraic structure theory of sequential machines" (1966) which —if, along with its successor Krohn-Rhodes theory seems to be largely impractical— is an interesting path-not-taken in CS...
- dhanna 4y ago
  I have a copy of this sitting in my parents basement along with a bunch of automata theory books I’ll probably never have the time to read
schoen 4y ago
One thing I learned from the obituary on Scott Aaronson's blog (https://scottaaronson.blog/?p=6622 https://scottaaronson.blog/?p=6622) is that Juris Hartmanis proved in 1965 (as a very early result in his career) that there are infinitely many separate complexity classes (both for time complexity and space complexity) for decidable computational problems. That is, for every problem that takes a certain amount of computational resources to solve correctly in general, there is always a harder (still solvable) problem that takes asymptotically more resources than that one. There is no hardest problem. That doesn't necessarily say anything about whether these problems would be of practical interest to human beings, but conceptually, there is an infinite hierarchy of complexity classes, and there can never been an algorithmic discovery that would make all of them equally hard to solve. https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Space_hierarchy_theorem https://en.wikipedia.org/wiki/Space_hierarchy_theorem Aaronson says that this guaranteed that "that the [then] new field of computational complexity theory would have a subject matter". He also notes that Richard Lipton and Ken Regan say that Hartmanis actually pioneered the concept of studying problems systematically in terms of the complexity classes they fall into. Hartmanis's original co-author, Richard Stearns, is still alive. https://en.wikipedia.org/wiki/Richard_E._Stearns https://en.wikipedia.org/wiki/Richard_E._Stearns
akchin 4y ago
Just saw this news here. He taught me at Cornell when I was a CS undergrad and I remember that class fondly. I still remember one of his office hours which was a day or two before thanksgiving. No one showed up except me and I remember thinking to myself - I am here by myself with a Turing award winner. Unreal!! He was a fantastic professor and person. RIP, professor Hartmanis

122 points by sizzle 4y ago

Lapsa 4y ago

name, surname sounds unmistakably Latvian. Turing award... and I didn't even know... rest in peace

b3kart 4y ago
Very mild, but also unmistakably Latvian accent. Was also surprised to learn about Juris. RIP indeed.

sireat 4y ago

Juris Hartmanis was Turing award winner laying out foundations for complexity theory. His life in his own words: https://cacm.acm.org/magazines/2015/4/184690-an-interview-wi https://cacm.acm.org/magazines/2015/4/184690-an-interview-wi... "I also discovered, during my education and early research experience, that you do not have to know that much to do research. With a good background education, one can very quickly absorb the necessary specialized knowledge for a specific research area. I think what Caltech really taught me was to be independent, and to try to go to the essence of a problem." In some ways a typical(and tragically sad) beginning for Latvian(and other Baltic) refugees at the end of WW2 but quite extraordinary achievements later on.

082349872349872 4y ago

Also cowrote "Algebraic structure theory of sequential machines" (1966) which —if, along with its successor Krohn-Rhodes theory seems to be largely impractical— is an interesting path-not-taken in CS...

dhanna 4y ago
I have a copy of this sitting in my parents basement along with a bunch of automata theory books I’ll probably never have the time to read

schoen 4y ago

One thing I learned from the obituary on Scott Aaronson's blog (https://scottaaronson.blog/?p=6622 https://scottaaronson.blog/?p=6622) is that Juris Hartmanis proved in 1965 (as a very early result in his career) that there are infinitely many separate complexity classes (both for time complexity and space complexity) for decidable computational problems. That is, for every problem that takes a certain amount of computational resources to solve correctly in general, there is always a harder (still solvable) problem that takes asymptotically more resources than that one. There is no hardest problem. That doesn't necessarily say anything about whether these problems would be of practical interest to human beings, but conceptually, there is an infinite hierarchy of complexity classes, and there can never been an algorithmic discovery that would make all of them equally hard to solve. https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Space_hierarchy_theorem https://en.wikipedia.org/wiki/Space_hierarchy_theorem Aaronson says that this guaranteed that "that the [then] new field of computational complexity theory would have a subject matter". He also notes that Richard Lipton and Ken Regan say that Hartmanis actually pioneered the concept of studying problems systematically in terms of the complexity classes they fall into. Hartmanis's original co-author, Richard Stearns, is still alive. https://en.wikipedia.org/wiki/Richard_E._Stearns https://en.wikipedia.org/wiki/Richard_E._Stearns

akchin 4y ago

Just saw this news here. He taught me at Cornell when I was a CS undergrad and I remember that class fondly. I still remember one of his office hours which was a day or two before thanksgiving. No one showed up except me and I remember thinking to myself - I am here by myself with a Turing award winner. Unreal!! He was a fantastic professor and person. RIP, professor Hartmanis