Juris Hartmanis 1928–2022
A sure foundation for Computational Complexity
|
| source—wonderful 2015 CACM interview |
Juris Hartmanis passed away this morning. He was a professor in Cornell’s computer science department since 1965. He won the 1993 Turing Award with Richard Stearns for their 1963–1965 paper “On the Computational Complexity of Algorithms.”
Today, Dick and I express our condolences and also appreciation for a long life and career shaping our field of computational complexity theory.
One mark of a long life is that the Complexity Theory Retrospective volume honoring his 60th birthday in 1988 was longer ago than the beginning of my tenure-track career at Buffalo in 1989. In the early 1980s, when I met both him and Alan Selman (who edited the volume), they were progenitors of the vein within computational complexity that emphasizes the structure of classes of problems.
I mean “progenitor” quite strongly: When I joined Cornell as a Mathematical Sciences Institute postdoc in 1986, the Computer Science Department generously gave me office space a few doors down from Juris in Upson Hall. I mixed with a gaggle of his students: Lane Hemaspaandra and Jim Kadin and Richard Chang and Desh Ranjan, also saw much of Jin-Yi Cai on his return visits, and had just missed Ming Li and Luc Longpré. We all amplified the energy that Juris brought to the field.
An Echo in Quantum
The structural framework needed to be filled with combinatorial power from other areas of mathematical sciences. But to see the framework’s longevity, one need look no further than the Best Paper in the 2022 Computational Complexity Conference and a paper just accepted to FOCS 2022 that was featured in Quanta:
- “The Acrobatics of BQP” by Scott Aaronson, DeVon Ingram, and William Kretschmer.
- “Verifiable Quantum Advantage Without Structure” by Takashi Yamakawa and Mark Zhandry.
Both are on quantum computing, a field that really began to exist about the time that Juris decided that Pankaj Rohatgi would be his last PhD student. The foci are problems involving Fourier transforms and their correlations, error-correcting codes, and the relationship of randomness to entropy that go well beyond what we thought of as “Structure.” Neither paper cites anything by Juris. Yet the former paper’s results are framed as complexity class relations that jump off the page—here are just three square centimeters of the abstract:
All three results in the latter paper are relative to a random oracle; the first states: “There are NP search problems solvable by BQP machines but not BPP machines.” The expansion of formal machine models from the basic Turing machine, in order to embrace elements of complexity, is the backbone of the paper with Stearns. The relation of machine models to classes in the presence of oracles was the focus of Juris’s ICALP 1986 paper with Lane, “Complexity Classes Without Machines.”
Founding Paper
My pithiest statement of the 1965 paper’s impact is that it made Turing’s tape-machine formulation durable. Indeed, the notions of streaming algorithms, nearly-linear time efficiency, and data locality being one-dimensional that I recall from the 1990s have more affinity to that paper’s technical development than to the polynomial benchmark of feasibility that yielded the formalizations of P and NP either side of 1970. Here are two machine diagrams from the paper:
Before giving the second diagram, let me note that their simple question of whether there is any algebraic irrational number that can be computed to 
The latter diagram conveys their proof of the Time Hierarchy Theorem—though needing a quadratic separation, as today’s logarithmic-gap formulation needed an improvement the following year by Stearns with Frederick Hennie. That is to say, the paper that defined complexity measures also demonstrated how it is possible to prove lower bounds for them.
It Could Have Been Lambdas
Lest you think the machine formulation was inevitable at the start, consider the following comment from “Mathai”—whom I take to be Mathai Joseph—in Lance Fortnow’s 2015 post marking the paper’s 50th anniversary:
“I talked to Hartmanis about this in 2012 and asked if they had considered using recursive function theory. He said they had and it had made things horribly complicated. Then they came across Turing machines and the whole thing became ‘so simple’ !”
I myself once took part in work trying to re-base complexity on recursion in an alteration of the lambda calculus. So many things have earned the name Turing tarpits; theirs based squarely on Turing was not.
Dick Karp, quoted by Stearns in his contribution to the 60th birthday volume, captured the paper’s importance:
[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory. Using the Turing machine as their model of an abstract computer, [they] provided a precise definition of the “complexity class” consisting of all problems solvable in a number of steps bounded by some given function of the input length
. Adapting the diagonalization technique that Turing had used to prove the undecidability of the Halting Problem, they proved many interesting results about the structure of complexity classes. All of us who read their paper could not fail to realize that we now had a satisfactory formal framework for pursuing the questions that [Jack] Edmonds had raised earlier in an intuitive fashion.
Dick and I have talked about the importance of good definitions often on this blog, and here is a similar post by Lance. In my formative years, I was fortunate to have two texts that wove theirs and the P-NP-based definitions together: [GJ79] and [HU79].
Undecidability and Proofs
A second vein of Juris’s work made a more particular impression on me, even before I met him. For SWAT (now FOCS) in 1967, he wrote a single-author paper, “On the Complexity of Undecidable Problems in Automata Theory.” The essence is that above a certain level of machine sophistication, whenever you prove the “good news” of lower bounds to separate classes in a hierarchy, you also get the “bad news” of there being problems between the class levels whose status is not resolvable in whatever strong system of logic you employ.
This raises the question, for classes like P and NP that have not yet been separated, whether the logical independence phenomenon washes over the entire landscape. He and John Hopcroft wrote a short paper for SIGACT News outlining this possibility. The topic was taken up by others, including Dick with Rich De Millo and later myself, and continues to percolate.
One of his last papers, “Computational Complexity and Mathematical Proofs,” takes the opposite avenue of how the structure of computations influences the production of proofs, including interactive proofs. This was based on an earlier paper with Chang, Ranjan, and Rohatgi, which I covered in a 2015 post. This diagram conveys the idea:
A Dinner Before Going to NSF
One of my most delightful memories is sitting next to Juris at the conference dinner at the IFIP 1994 congress in Hamburg. Earlier that day I had met the conference honoree, Konrad Zuse, even speaking a little in German with him. We were not seated close to Zuse—indeed, I am not confident to say either way whether he was there. But seated across from us was a woman representing the NSF whom Juris was most interested to talk with.
The strong memory I have is that I did not commandeer the conversation toward technical problems within structural complexity. Juris was eager to convey command and interest in the breadth of Computer Science, and so was I. We three went further: into music and art and culture quite apart from computers. It was a delightful flow of talk for almost two hours. Juris thanked me afterward for not waxing technical. I did not fully get the picture until Juris joined NSF as Director of CISE two years later, in 1996.
There is much more I could say about his work promoting the complexity theory community, about being a founding editor of the Springer-Verlag Lecture Notes in Computer Science series, about helping to found Cornell’s computer science department. On the last, his longtime Cornell colleague Anil Nerode has sent me this:
“I was chairman of the committee of three, which included Bob Walker, that selected him to chair and organize a new computer science department. He already exhibited the scientific and people skills, and the breadth of vision, for which he was later famous. I will miss him very much.”
One other detail I remember of Juris’s personal life is that he liked sporty cars. I am not among those who rode with him muscularly in one—other drivers have filled that niche for me. We invite readers who have done so—or who wish to give any other personal reminiscences—to contribute below. I’ll leave with the observation that of the two scientists in this photo—
|
| “A Great Man and a Statue” source |
—it was as much in Juris’s nature to wear a tie as it was for the other guy not to.
Open Problems
Again we give our condolences to his family and surviving colleagues, which set includes the three acknowledged at the end of the 1967 paper mentioned above:
[some small tweaks]
I met Hartmanis at the University of Iowa, where he must have been a visitor. I was then a Lecturer at Berkeley and tried to interest him in my “Properties of Algorithms” lectures for beginning students. Our conversation never got anywhere, it was too basic for him, but he was extremely nice and heard me out, noting that he hadn’t thought about the stuff I mentioned. That was amazingly humble of him, given his accomplishments noted in this article.
Very sad news. His work had a very strong influence on me.
Likewise. His work and he as a person had a very strong influence on my husband, Alan Selman. I enjoyed his company when I attended conferences with Alan. He was quite the gentleman.
I think Juris was the Chair when I joined Cornell in 1981. I remember him holding court in the lunch gatherings in the Rathskeller. One day there was a rare fall of powder snow, so I and some junior faculty friends (Skeen, Babaoğlu, Toueg – everyone was called by their surname) sneaked away to ski, feeling a bit guilty. Only to see Hartmanis gliding down the main slope when we arrived. He was a fine skier, and loved life. An old school European gentleman. RIP.
I was a grad student at Cornell 67-69 and 72-75 (Vietnam interrupted my stint) and Hartmanis was both an excellent teacher and a kind leader. Because of my career path, he ended up being my committee chairman. These are my two favorite memories.
During my oral qualifier, he asked me a complexity question about some particular formulation of tapes and problem — the details escape me. I struggled with it for 10 to 20 minutes with all my solution attempts circling back around to the starting place. Eventually, Hartmanis stopped me and my heart sank — I figured I had fumbled some easy question. Then he said, “If you figure it out, come tell me. I need that result for a paper I’m writing.” Turns out I passed after all.
My second memory involves a favor he did for me. Before I finished my dissertation, I had already started teaching at UC Davis in their graduate computer science program. When I came back to Cornell for my defense, I told Hartmanis that we had a graduate student seminar series and that it would be wonderful if, when he happened to be around San Francisco, he could come give a talk. Then I didn’t think anything more about it.
Some time later, I got a call (no emails then) asking if the offer still stood. Of course it did. We made the arrangements, picked him up somewhere to drive to our Livermore campus, spent time with during the day, he gave the talk and took part in the after talk wine-and-cheese session (a tradition adopted from Cornell), and then some faculty and students took him to dinner somewhere, probably in Berkeley. At the end of the evening, I asked what else he had planned for his trip. Hartmanis then told me that he was flying back to Ithaca the next day. It seems that he had some free time and he came all the way cross country just to help one of his students “bump” the career along a bit. It was such a generous and thoughtful thing to do and, had I not asked him, his thoughtfulness would never even have been known.
Hartmanis was brilliant, funny, a wonderful teacher. But even more, he was a kind and caring man. I think of him often. I will miss him.
It is so amazing that such people still live in this world!
My condolences to the entire TCS community.
Juris was instrumental in the rather accidental switch which turned me from a pure mathematician into a Complexity Theory researcher. In 1971 I had the chance to make a few daytrip visits to Cornell with the purpose of learning about the then erupting field of computer science.
Upon arrival I met Juris (to which a mathematcs colleague had provided me an introduction). I left with a preliminary version of the 1971 survey paper on abstract complexity theory.
Studying it I stumbled onto something which seemed to be an error (in fact it was just an unfortunate way of explaining some details) in the proof of the McCreight-Meyer naming theorem in this paper. Back in Holland I did a complete analysis of the proof and figured out what was the problem. This lead to my subsequent ph.d. thesis on Abstract complexity theory which I defended in Amsterdam in 1974. Juris was co-referee on this occasion; of my three supervisors the uniquer one who worked in the field.
My contacts with Juris have remained since. We have met at various TCS conferences both in the US and Europe. After my defence I stayed for three months in Cornell, but the main result of this visit was the discovery of what now is known as the Van Emde Boas tree structure. Later I have made several visits to Cornell including the retirement party in 2001. But also at the occasion of the 60 years birthday party for Dexter Kozen I came to Cornell and I have met him there. That must have been our last encounter.
This departure closes an era. Now all my three advisors have left earth.
Peter van Emde Boas
Heemsted, the Netherlands.
This is very sad news. I served on the CISE Advisory committee while Juris was Director of CISE. Later, in 2008 when there was a paucity of academic openings in computer science, Juris was selected to speak at a CRA workshop for graduating PhDs in computer science – 1800 new PhDs and fewer than 150 academic openings. He dragged me along to speak on opportunities for underrepresented minorities in computing. Instead of doom and gloom, he was inspirational and hilarious. His lived experience was inspirational and he had a wonderful (but under-reported) sense of humor. I feel very fortunate that I had the opportunity to know him.
Prof. Juris Hartmanis was a giant in our field, a life long teacher and mentor to me, a dear friend, and a great gentleman. I was one of his former students. In person, he was always kind, warm, and caring. He was particularly kind to people who were not yet well established. His foundational work established and shaped our complexity field, and continues to inspire complexity theorists worldwide. To us students, he imparted not just technical knowledge, but also, perhaps more importantly, an elevated perspective. I wish I could absorb his wisdom as readily as he imbued them in his everyday conversations and interactions. His piercing insight and wit often cut away the chaff (and cut to the chase, and may cause some mild discomfiture to the uninitiated, but always for the greater good…) One magic ability of Juris is that he can often convince people what is the right course of action, and also convince them that it was in their own best interest, and perhaps it was their own idea to start with! And in hindsight, he was often proved 100% right.
A truly great teacher, and leader. It is the great honor in my life to have had the opportunity to be one of his PhD students. I will miss him dearly.
Sorry to hear that. Hartmanis and Stearns work on factoring state machines is sorely unappreciated. I heard Hartmanis speak once, when he was visting U. Mass and among other things I learned from his talk was the idea of the SPU – the smallest publishable unit, which made me laugh but make some other people in the audience a little uncomfortable.