Archive for the ‘Uncategorized’ Category

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.

On defeating a sociopath

Monday, November 9th, 2020

There are people who really, genuinely, believe, as far as you can dig down, that winning is everything—that however many lies they told, allies they betrayed, innocent lives they harmed, etc. etc., it was all justified by the fact that they won and their enemies lost. Faced with such sociopaths, people like me typically feel an irresistible compulsion to counterargue: to make the sociopath realize that winning is not everything, that truth and honor are terminal values as well; to subject the sociopath to the standards by which the rest of us are judged; to find the conscience that the sociopath buried even from himself and drag it out into the light. Let me know if you can think of any case in human history where such efforts succeeded, because I’m having difficulty doing so.

Clearly, in the vast majority of cases if not in all, the only counterargument that a sociopath will ever understand is losing. And yet not just any kind of losing suffices. For victims, there’s an enormous temptation to turn the sociopath’s underhanded tools against him, to win with the same deceit and naked power that the sociopath so gleefully inflicted on others. And yet, if that’s what it takes to beat him, then you have to imagine the sociopath deriving a certain perverse satisfaction from it.

Think of the movie villain who, as the panting hero stands over him with his lightsaber, taunts “Yes … yes … destroy me! Do it now! Feel the hate and the rage flow through you!” What happens next, of course, is that the hero angrily decides to give the villain one more chance, the ungrateful villain lunges to stab the hero in the back or something, and only then does the villain die—either by a self-inflicted accident, or else killed by the hero in immediate self-defense. Either way, the hero walks away with victory and honor.

In practice, it’s a tall order to arrange all of that. This explains why sociopaths are so hard to defeat, and why I feel so bleak and depressed whenever I see one flaunting his power. But, you know, the great upside of pessimism is that it doesn’t take much to beat your expectations! Whenever a single sociopath is cleanly and honorably defeated, or even just rendered irrelevant—no matter that the sociopath’s friends and allies are still in power, no matter that they’ll be back to fight another day, etc. etc.—it’s a genuine occasion for rejoicing.

Anyway, that pretty much sums up my thoughts regarding Arthur Chu. In other news, hooray about the election!

Updates from Kenya

Wednesday, January 18th, 2012

Yes, I’m blogging from outside Nairobi, where I’ve come to investigate the true circumstances of President Obama’s birth.  Seriously, Dana and I are here to go on a safari for our belated honeymoon—for both of us, it’s our first non-work-related trip in many years.  Needless to say, we both brought our laptops.

Like everyone else with an ounce of sense, I’m absolutely horrified by SOPA, and inspired by the way so many Internet companies and organizations have banded together to try to prevent the United States from moving in the direction of China and Iran.

Meanwhile, on the theme of open access to information on the web, check out a New York Times article by Thomas Lin about the open science movement.  I’m quoted briefly toward the end.

Sorry for the light (nonexistent) blogging lately.  I’ll be back after I’m done with the lions and hippos and so forth.

Discussion questions about Watson

Thursday, February 17th, 2011
  1. Wouldn’t Jeopardy! be better without those stupid buzzers?  Even if the contestants just, y’know, took turns?  In a game focused solely on question-answering (OK, OK, answer-questioning) rather than buzzing, Watson would still have done amazingly well and reflected credit on its developers, but the man/machine competition would have been much closer and much more interesting to watch.  No one needs a repeated demonstration that computers have faster reaction times than humans.
  2. Inspired by the timeline discussion: could something like Watson have been built in, say, 2000?  If not, then which developments of the past decade played important roles?
  3. Back when Deep Blue beat Kasparov, IBM made a big to-do about the central role played by its large, specially-designed mainframe with custom “chess chips”—but then it wasn’t long before programs like Deep Fritz running on desktop PCs produced similar (and today, probably superior) performance.  How long before we can expect a computer Jeopardy! champion that fits behind the podium?

My TEDxCaltech talk

Wednesday, February 16th, 2011

A month ago, Caltech hosted a daylong event called “TEDxCaltech / Feynman’s Vision: the Next 50 Years”, which was attended by about a thousand people. Celebrity participants included Stephen Hawking, Carl and Michelle Feynman (Carl told me he’s a fan of the blog—hi Carl!), and Ondar, a Tuvan throat-singer who pretty much stole the show.

Videos are finally being posted on YouTube; my talk is here. My goal was to cover the P versus NP question, quantum computing, conceptual issues in quantum mechanics, and Feynman’s relation to all three, while also cracking crude masturbation jokes (in a talk like this, one has to bring out the heavy humor cannons), and to finish in 15 minutes. I don’t know how well I succeeded—but if I die tomorrow, then at least Stephen Hawking was in the audience when I made my case for P and NP being as big a deal as anything in physics.

Two explanatory comments:

  • By far my most successful joke was a reference to “prime numbers, such as 3, 5, 1…” Before the lunch break, the emcee had told everyone to be back by 1:35, “which I’m sure you nerds will remember since it’s the first three prime numbers.”
  • Yeah, I know the current upper bound on the matrix multiplication exponent is 2.376, not 2.736! It was correct on the slides I submitted, but got transposed when the slides were converted into “TED format.”

If you think my talk stinks, my only defense is that showing up to give it was already an accomplishment: my flight (from Tel Aviv to LA through Newark) was canceled because of a snowstorm, so I arrived at Caltech exhausted and barely conscious, via a 36-hour alternate route through Frankfurt and London.

I have to confess that I was skeptical of this event’s entire premise. Richard Feynman was famous for his contempt of pomp and authority; would he really have enjoyed a heavily-scripted day extolling him as a secular saint? In the end, though, the quality of many of the talks made the event more than worthwhile for me, even without counting Ondar’s throat-singing as a “talk.” I particularly enjoyed the cosmology talk of fellow-blogger Sean Carroll (yo, Sean), the Feynman stories of Lenny Susskind, a demonstration of the mind-blowing WorldWide Telescope by Curtis Wong of Microsoft, and a “Who Wants to be a Millionaire?” parody skit put on by the three “black hole bettors” (John Preskill, Kip Thorne, and Hawking, the last of whom wheeled into the auditorium to thunderous applause and the opening fanfare of Thus Spake Zarathustra). I understand that all the talks will eventually be on YouTube here.

Thanks to Michael Roukes, Mary Sikora, John Preskill, Ann Harvey, and the other organizers for putting this thing together and for inviting me.