Juris Hartmanis (1928-2022): Guest post by Ryan Williams
Saturday, July 30th, 2022
Scott’s Introduction
Juris Hartmanis — one of the founding figures of theoretical computer science, winner of the Turing Award, cofounder of the Cornell computer science department (of which I’m an alumnus), cofounder of the Conference on Computational Complexity or CCC (which I just attended), PhD adviser to many of the leading complexity theorists — has passed away at age 94.
Scientifically, Hartmanis will be remembered as long as our field exists for several contributions. First and foremost, his 1965 proof, with Richard Stearns, of the time and space hierarchy theorems, which adapt Turing’s undecidability theorems to show that there exist computable problems that are arbitrarily hard (and thus, if you like, that the new field of computational complexity theory would have a subject matter). Second, his and Berman’s investigation, in the 1970s, of the detailed structure of NP-complete problems (are they “paddable”? can they be sparse? are all NP-complete sets polynomial-time isomorphic? or as we now believe, are they not?), which helped start the whole area of “structural complexity theory” (the original subject matter of the CCC conference). Third, his investigations of logic and complexity theory, including whether problems like P vs. NP could be independent of the axioms of set theory, and the relations of that question to relativization and oracles.
As this memorial post by Richard Lipton and Ken Regan points out, some of Hartmanis’s most important contributions are so basic that it feels weird today even to mention them explicitly: the use of Turing machines to model computational complexity (!). The study of complexity via “complexity classes,” consisting of all problems solvable within a given resource bound. The whole Complexity Zoo could’ve been renamed Jurisic Park.
One of my regrets in life is that I didn’t get to know Hartmanis well when I was an undergrad at Cornell. (This was a stage of my life when I was still intimidated by my professors, or hyper-mega-intimidated if they were Juris Hartmanis.) I actually conversed with him more after I’d graduated and returned for visits. He was so considerate and kind, almost grandfatherly, that I realized how foolish I was not to have sought him out as a student.
There was, however, another undergrad at Cornell at the same time as me, who wasn’t quite as intimidated as I was, and who ended up doing an independent study with Hartmanis, about the possibility of complete problems for NP∩coNP if I remember correctly. This undergrad’s real goal was to solve the P vs. NP problem, which might sound ridiculous until I tell you that his name was Ryan Williams. I asked Ryan to share his own memories of Juris, and he’s graciously done so below. You won’t regret reading this. —SA
Juris Hartmanis by Ryan Williams
I am extremely sad that Professor Juris Hartmanis has passed away. He made an enormous impact on my early career, and on my growth as a scientist: arguably, I wouldn’t be a scientist at all without him. He was extraordinarily gentle, inspiring, and encouraging to me.
My story of how I know Professor Hartmanis is really my “origin story” as a theoretical computer scientist. So I’ll tell you a little about the situation before I met him, to give some before/after context.
As a freshman at Cornell learning math and computer science, I became captivated by P vs NP and P vs PSPACE. In my teenage hubris, I planned it out: in the spring I’d take discrete math, fall I’d take the intro to theory of computing, and the following spring I’d take the grad complexity course being taught by Prof. Hartmanis that term. After that, I’d go to grad school in theory, and somewhere along the way tackle P vs NP. Simple enough…
I did fine in discrete math, but struggled in intro to theory, partly due to the fact that the lectures (and exams) were at 9am. I managed to do well on the final and earned a B+. I began to wonder if my plan was unsound. I went to the instructor and told them of my plan. They recommended that I should not try for grad school, as I didn’t seem to be particularly talented and there were “no jobs in theory”. (Jobs? Who needs jobs?) I asked if my chances of getting in grad school would be improved if I did well in the grad complexity class. They said “maybe”, and that was enough to keep me going.
The vibe in Prof. Hartmanis’ class was amazing. He was exceptionally passionate about teaching complexity. His lectures were a revelation; they were exhilarating. He stayed laser-focused on communicating the heart of the ideas, with brevity and levity as needed to avoid the technical details (often nasty in the case of Turing machines). In the margins of my own class notes, I jotted down countless one-liners and antics. One of my favorite memories is that, when he wanted to be done with a proof and was tired of further questions, he would write his Q.E.D. symbol very large, with a little intimidating devil inside of it, like so:
As he’d often be packing more material in the lecture than time allowed, he joked that he wasn’t responsible for what was said in the last five minutes of class (when he’d rush to cover what remained). He was having so much fun with the material, and he repeatedly showed that one could think about these very deep and complex things very simply. My intuition for complexity grew so fast that the rest of my mathematical education was lifted immeasurably by it.
In response, I began to take my studies very seriously that semester. I showed up to every session of his office hours. I peppered him with questions after class. He was unwaveringly patient, helping me sort out my latest confusion. Eventually my questions turned into actual research problems, which occasionally received interesting answers (mostly already answered in the literature). After the semester ended, I began to schedule weekly meetings with him, discussing anything and everything complexity. He always seemed happy to chat, and during conversations he made the development of my research taste a top priority. He made it clear when what I was saying was interesting to him, and when it wasn’t… and if it wasn’t, I needed to explain why I found it interesting. But I understood that all of this was for my education as a future theoretical computer scientist, which he treated as inevitable.
I don’t know why Professor Hartmanis believed in me. During that period in my life, I felt like nobody else did, and it felt odd that the Turing Award winner was the one who believed the most. On the coattails of his eager recommendation, I was able to attend an REU at DIMACS. Later he was shocked and annoyed when in spite of his letter, I was rejected from every grad school I applied to (I suppose the B+ didn’t help). However, probably owing to Prof. Hartmanis’ stature at the NSF, I was still awarded an NSF grad fellowship. When I told him of the good and bad news, and that I had no Plan B, he immediately picked up the phone and called someone explaining the situation. He hung up and announced “Congratulations Ryan, you have been admitted to the MEng program.” So I spent the next year in Ithaca as an MEng student. He informed me he was retiring, and maybe grad programs are getting skeptical of complexity. Maybe I should try to sneak in by studying something adjacent. He suggested working with Bart Selman on SAT (which I did). My confidence was shaken by the rejections but, seeing how strongly he believed in me, I could not let him down.
He was always full of affirmations for me, with a trademark mix of humor and motivation. After I would report a batch of new observations, he would say something like: “As they say, the biggest pig eats the most potatoes. And you sir, are a very big pig!” After I had a paper accepted to SODA, he declared that I was now a computer scientist. After I had a paper accepted to IJCAI, he declared that I had become a world-famous computer scientist. Prof. Hartmanis remained my strongest champion and loudest cheerleader in research, until I was finally admitted to some grad schools the next time around.
I’m immensely grateful to have known him. Without his faith, I’d have never become a theoretical computer scientist. Without his initial influence, I’d have never been a good one. I’ve been writing entirely through tears; I hope for everyone reading that they too have the chance to impact a young person’s life so profoundly.
SA’s Endnotes
Besides the obituary by Lipton and Regan, see also the obituary by Bill Gasarch. And especially check out Hartmanis’s extraordinary biographical essay from 2015, in which he describes his childhood in Latvia; his father being taken away by the Soviets to be executed when he was 12 years old; his move to America with his mother, where he worked as a steelworker and a butler while he studied at the University of Kansas City; Caltech’s farsighted decision to admit him as a graduate student despite his unusual background; and then the beginnings of computational complexity theory and the rest of his distinguished career.
Follow