Juris Hartmanis (1928-2022): Guest post by Ryan Williams
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
Comment #1 July 30th, 2022 at 11:40 pm
Coincidentally and having nothing to do with the thrust of this post I also worked with Bart Selman on SAT, back when I was in high school.
Comment #2 July 31st, 2022 at 8:34 am
Where were all these warm and grandfatherly, considerate mentors when I was at University?! Well maybe you have to be of a certain talent level to be deserving of them.
Well, just idle curiosity, did most of you others have such seminal mentors at some point in college?
I’m pausing to wonder which way is the direction of causality here. Most successful academics seem to have at least one and some even more of such great mentors that took an interest in them.
Do they get this mentorship because they are good and the mentors spot it? Or are the lucky to get a good mentors attention and hence they become successful academics later.
Would love to hear from others. Especially would love to hear from people who didn’t become so academically sucessful who also hadd a great mentor take interest in them. Do such stories exist?
Comment #3 July 31st, 2022 at 1:25 pm
I had a great professor for E&M. Dr. Vohrmann? Something like that. His discussion of Special Relativity inspired me to come up with my own proof (by reductio ad absurdum) which I wrote on the big cardboard sheet that a dry-cleaned shirt came in at that time, and went to his office during office hours to show it to him.
He was eating a sandwich, having worked through lunch or something, so it didn’t seem a convenient time. He listened and didn’t comment except to say that RAD proofs are always a bit unsatisfactory or unfulfilling or something like that. That is, he was polite but not very interested. It turned out that was his last class at MSU. He moved to RPI and coincidentally I once saw him in a building there when I was getting my MME.
We had a real genius in that class, a 14-year old who later finished high in the Putnam Math Competition. Dr. V had given us an assignment to calculate the amount of energy released in one hydrogen-helium fusion, from the known masses of the components. The genius said he didn’t understand how to do the assignment. Dr. V said what I would have said, it’s simple, just add the masses of two hydrogen atoms and subtract the mass of a helium atom. The genius plaintively replied, “But how do we know it is two hydrogen atoms?” Dr. V paused, then said, “I stand corrected.” He went on to explain that other experiments which he hadn’t mentioned indicated that.
Comment #4 August 1st, 2022 at 10:25 am
In my opinion, there are many ideas in Hartmanis’s papers that have not yet been milked dry. Top on my list is his paper (with Chang, Kadin, and Mitchell), “Some observations about relativization of space bounded computations.” This paper has surprisingly few citations. Space-bounded complexity has received less attention than other concepts such as circuits or nondeterminism, and it is my belief that the ideas in this paper could lead to a breakthrough if we could just figure out how to extend them, or combine them in the right way with other ideas.
Comment #5 August 1st, 2022 at 11:09 am
Thanks for writing this, the both of you. It is always welcome to read tributes from individuals such as yourselves with close connections both to the work of the person who has passed and to the person themselves.
Comment #6 August 1st, 2022 at 12:34 pm
Thank you, Scott, for inviting Ryan Williams to guest post, and thank you, Ryan, for what you wrote. I first met Prof. Hartmanis in 1990, when I was a sophomore at Cornell, taking his CS 481: Theory of Computation class. It was my first exposure to this material and though I didn’t place it at the center of my career, or choose to investigate any of the delicious (and devilish) open problems, he breathed such life into the subject that it has remained dear to me, even after 32 years. Aside from Prof. Hartmanis’ gentleness, joy, and humor that Ryan recounted so well — and thank you for reminding me of his signature QED! — what staggered me was the clarity of his lectures, always in full contact with the essential nature of computation. The delightful, and for me, no less astonishing, outcome was that I understood his lectures! In an academic context, it was the first time I experienced feeling intelligent for the right reasons, categorically distinct from the experience of having cloaked oneself in a high entropy language, festooned with jargon, or of having been sufficiently bludgeoned so as to be handed the shibboleth to a priesthood. So Prof. Hartmanis’ class was crucially also my first exposure to a master teacher. In CS 481, the lectures disappeared! Richard Feynman died two years before I met Prof. Hartmanis, and although I didn’t have the privilege to attend any of Feynman’s lectures in person, I suspect much of what I feel toward Prof. Hartmanis — the awe, sure, but also gratitude for what he created in class: total, unadorned engagement with the beautiful and profound ideas he taught — is what those lucky Caltech freshmen felt attending Feynman’s lectures on physics. The day is darker knowing Prof. Hartmanis’ mind and voice are no longer at play in the world. Goodbye.
Comment #7 August 1st, 2022 at 6:06 pm
That was a beautiful and moving essay, Ryan — thank you.
Comment #8 August 2nd, 2022 at 6:55 am
I was interested to learn of his work with Stearns on finite automata, anticipating the Krohn-Rhodes theorem.
Comment #9 August 4th, 2022 at 3:51 pm
Here is Cornell’s announcement about Hartmanis’s death: “Juris Hartmanis, first CS department chair, dies at 94,” https://prod.cis.cornell.edu/juris-hartmanis-first-cs-department-chair-dies-94. There will be a celebration of his life at the Ithaca Yacht Club on Monday, Aug 15; for details and other memorial info (including an online “Tribute Wall”), see: https://www.bangsfuneralhome.com/obituary/Juris-Hartmanis.
Comment #10 August 11th, 2022 at 4:11 am
I just want to say that I loved Rahul’s (#2) comment. I would love for people to pitch in. Rahul asks for people who had great mentors take interest in them, but were ultimately “unsuccessful”. I am also interested in the other kind, if there are any – people who never had great mentors take an interest in them, but were successful.
My impression is this – w.h.p someone who is successful is “worth it”, but only a small fraction of people “worth it” become successful. Also, I don’t think a “great mentor” is a necessary condition. Just encouragement and good advice is good enough, even if it is comes from a “non-great mentor”.