Happy 90th Juris!

Juris Hartmanis turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work On the Computational Complexity of Algorithms. I've talked about that paper before, after all it started our field and gave the name that we use for the blog. So instead I'll use this blog post to talk about how Hartmanis led me into this wondrous field.

At Cornell in 1983 I was an undergraduate double major in math and CS destined at the time for grad school in math. I took the undergraduate Introduction to Theory course from Hartmanis and immediately got excited about the field. Hartmanis said the top student in the course was typically an undergrad followed by a bunch of graduate students. I was a counterexample coming in second in the course list (back then your grades were posted by ID number). I never found out who came in first.

In that same semester I took Introduction to Linguistics. Chomsky and context-free languages in both classes. Seemed cool at the time.

Based almost solely on that course with Hartmanis I decided to do graduate work in theoretical computer science. In the spring of 1985, while most of my fellow second-semester seniors took Introduction to Wine, I took graduate Complexity Complexity again with Hartmanis. That cemented my career as a complexity theorist. The course started with some basic computability theory (then called recursion theory) and used that as a jumping point to complexity. A large emphasis on the Berman-Hartmanis Isomorphism Conjecture. The conjecture implies P ≠ NP and Hartmanis said anyone who could prove the conjecture, even assuming P ≠ NP, would get an automatic A. The problem remains open but I did years later have a couple of proofs giving an oracle making BH true. That should be good enough for a B.

My favorite quote from Juris: "We all know that P is different from NP, we just don't know how to prove it." Still true today.