Steven Rudich (1961-2024)
I was sure my next post would be about the election—the sword of Damocles hanging over the United States and civilization as a whole. Instead, I have sad news, but also news that brings memories of warmth, humor, and complexity-theoretic insight.
Steven Rudich—professor at Carnegie Mellon, central figure of theoretical computer science since the 1990s, and a kindred spirit and friend—has died at the too-early age of 63. While I interacted with him much more seldom than I wish I had, it would be no exaggeration to call him one of the biggest influences on my life and career.
I first became aware of Steve at age 17, when I read the Natural Proofs paper that he coauthored with Razborov. I was sitting in the basement computer room at Telluride House at Cornell, and still recall the feeling of awe that came over me with every page. This one paper changed my scientific worldview. It expanded my conception of what the P versus NP problem was about and what theoretical computer science could even do—showing how it could turn in on itself, explain its own difficulties in proving problems hard in terms of the truth of those same problems’ hardness, and thereby transmute defeat into victory. I may have been bowled over by the paper’s rhetoric as much as by its results: it was like, you’re allowed to write that way?
I was nearly as impressed by Steve’s PhD thesis, which was full of proofs that gave off the appearance of being handwavy, “just phoning it in,” but were in reality completely rigorous. The result that excited me the most said that, if a certain strange combinatorial conjecture was true, then there was essentially no hope of proving that P≠NP∩coNP relative to a random oracle with probability 1. I played around with the combinatorial conjecture but couldn’t make headway on it; a year or two later, I was excited when I met Clifford Smyth and he told me that he, Kahn, and Saks had just proved it. Rudich’s conjecture directly inspired me to work on what later became the Aaronson-Ambainis Conjecture, which is still unproved, but which if true, similarly implies that there’s no hope of proving P≠BQP relative to a random oracle with probability 1.
When I applied to CS PhD programs in 1999, I wrote about how I wanted to sing the ideas of theoretical computer science from the rooftops—just like Steven Rudich had done, with the celebrated Andrew’s Leap summer program that he’d started at Carnegie Mellon. (How many other models were there? Indeed, how many other models are there today?) I was then honored beyond words when Steve called me on the phone, before anyone else had, and made an hourlong pitch for me to become his student. “You’re what I call a ‘prefab’,” he said. “You already have the mindset that I try to instill in students by the end of their PhDs.” I didn’t have much self-confidence then, which is why I can still quote Steve’s words a quarter-century later. In the ensuing years, when (as often) I doubted myself, I’d think back to that phone call with Steve, and my burning desire to be what he apparently thought I was.
Alas, when I arrived in Pittsburgh for CMU’s visit weekend, I saw Steve holding court in front of a small crowd of students, dispensing wisdom and doing magic tricks. I was miffed that he never noticed or acknowledged me: had he already changed his mind about me, lost interest? It was only later that I learned that Steve was going blind at the time, and literally hadn’t seen me.
In any case, while I came within a hair of accepting CMU’s offer, in the end I chose Berkeley. I wasn’t yet 100% sure that I wanted to do quantum computing (as opposed to AI or classical complexity theory), but the lure of the Bay Area, of the storied CS theory group where Steve himself had studied, and of Steve’s academic sibling Umesh Vazirani proved too great.
Full of regrets about the road not taken, I was glad that, in the summer between undergrad and PhD, I got to attend the PCMI summer school on computational complexity at the Institute for Advanced Study in Princeton, where Steve gave a spectacular series of lectures. By that point, Steve was almost fully blind. He put transparencies up, sometimes upside-down until the audience corrected him, and then lectured about them entirely from memory. He said that doing CS theory sightless was a new, more conceptual experience for him.
Even in his new condition, Steve’s showmanship hadn’t left him; he held the audience spellbound as few academics do. And in a special lecture on “how to give talks,” he spilled his secrets.
“What the speaker imagines the audience is thinking,” read one slide. And then, inside the thought bubbles: “MORE! HARDER! FASTER! … Ahhhhh yes, QED! Truth is beauty.”
“What the audience is actually thinking,” read the next slide, below which: “When is this over? I need to pee. Can I get a date with the person next to me?” (And this was before smartphones.) And yet, Steve explained, rather than resenting the many demands on the audience’s attention, a good speaker would break through, meet people where they were, just as he was doing right then.
I listened, took mental notes, resolved to practice this stuff. I reflected that, even if my shtick only ever became 10% as funny or fluid as Steve’s, I’d still come out way ahead.
It’s possible that the last time I saw Steve was in 2007, when I visited Carnegie Mellon to give a talk about algebrization, a new barrier to solving P vs. NP (and other central problems of complexity theory) that Avi Wigderson and I had recently discovered. When I started writing the algebrization paper, I very consciously modeled it after the Natural Proofs paper; the one wouldn’t have been thinkable without the other. So you can imagine how much it meant to me when Steve liked algebrization—when, even though he couldn’t see my slides, he got enough from the spoken part of the talk to burst with “conceptual” questions and comments.
Steve not only peeled back the mystery of P vs NP insofar as anyone has. He did it with exuberance and showmanship and humor and joy and kindness. I won’t forget him.
I’ve written here only about the tiniest sliver of Steve’s life: namely, the sliver where it intersected mine. I wish that sliver were a hundred times bigger, so that there’d be a hundred times more to write. But CS theory, and CS more broadly, are communities. When I posted about Steve’s passing on Facebook, I got inundated by comments from friends of mine who (as it turned out) had taken Steve’s courses, or TA’d for him, or attended Andrew’s Leap, or otherwise knew him, and on whom he’d left a permanent impression—and I hadn’t even known any of this.
So I’ll end this post with a request: please share your Rudich stories in the comments! I’d especially love specific recollections of his jokes, advice, insights, or witticisms. We now live in a world where, even in the teeth of the likelihood that P≠NP, powerful algorithms running in massive datacenters nevertheless try to replicate the magic of human intelligence, by compressing and predicting all the text on the public Internet. I don’t know where this is going, but I can’t imagine that it would hurt for the emerging global hive-mind to know more about Steven Rudich.
Follow
Comment #1 November 2nd, 2024 at 10:04 pm
This is exceptionally beautiful writing. This person I will never know, came alive in this post as an amazing person. What a tribute!
Comment #2 November 3rd, 2024 at 5:00 pm
Oh my, very sad to hear thiss. As an undergrad at CMU years ago, I took both his introductory math / theoretical CS course and his grad Complexity Theory course. And at the time at least, these were really *his* courses, he had clearly spent a lot of effort thinking about how to teach them. A thing I really loved was his desire to take complex and abstract ideas and try to distill them down to as much as possible to what was really essential about them. In many cases he would make an initial quite subtle idea seem very natural, and then only after you got a bit more dirty with it did you realize how carefully he had explained it.
Comment #3 November 4th, 2024 at 9:31 am
I was a CS-curious chemistry major at CMU and my biggest regret was never taking 15-251 (Great Theoretical Ideas in CS). It had a very intense reputation which unfortunately scared me away. People tended disappear when they were taking the class – “I have 251 work” excused you from all social obligations for a semester – but those people would then emerge afterward enlightened. A course like that is an amazing legacy.
If anyone is like me and is curious, it looks like a version of the course is available online at cs251 dot com.
Comment #4 November 5th, 2024 at 11:58 pm
I was so sad to hear of Steven’s passing. And thank you, Scott, for your eloquent recollections.
I knew Steven in 1997 when I was deciding where to go for grad school, and then in his complexity class at Berkeley in the fall semester. For someone I only knew for about a year, the number of things I recall from our conversations is striking — he made a very large impression on me, and his advice steered me in a positive direction. I remember his excitement in teaching complexity, and about a result Ambainis proved during the semester. Most of all, I remember the irrepressible twinkle in his eyes and the sense of magic that it conveyed. I’m very sad that he’s no longer with us.
Comment #5 November 9th, 2024 at 2:57 pm
I knew Steven since he was an undergraduate at Wesleyan. Too many stories. But I think this will be of interest here.
Steven told me how he solved problems. When he was a graduate student at Berkeley, he would pose/share problems to the other graduate students. The likes of Umesh Vazirani, Noam Nisam, Shafi Goldwasser, Moni Naor and or course Russel Impagliazzo. He would carefully observe how each friend attacked the problems. Then, according to Steven, whenever he himself confronted a problem he would systematically ask himself: What would Umesh try? What would Noam try? What would Shafi try? etc.
Comment #6 November 11th, 2024 at 4:53 pm
His work of course inspired me, like many, but I met Steven only once when I visited CMU around 2011. I remember going on a walk with him (possibly to eat?), and talking about how one might use complexity theory to formalize what it meant for something to be “hard to understand”. It was really wonderful to talk to someone who seemed to be thinking such Big Thoughts; so much so that I still remember it today, despite only ever having met him the one time.
Comment #7 November 11th, 2024 at 5:52 pm
Rudich went to my high school (about twenty years before I did) and I remember one of the teachers telling me “one of our alums is a very famous computer scientist”.
Then when I was a Berkeley undergrad, he was visiting at Berkeley and he taught his undergraduate discrete math course, and I got to take it. I was having a hard time then, and it was hard for me to enjoy any of my courses as much as I would have liked, but it was definitely an excellent course. Rudich met with me once or twice outside of class and was very encouraging.
Then when I was a Berkeley dropout, I was attending an event in Pittsburgh and I looked him up. He ended up hosting me at his house for several hours. It seemed like *he* was having a pretty hard time at that moment. But he was still very gracious and always encouraging.
I’m sorry that I didn’t know more CS theory to talk over with him, because he was obviously one of the great luminaries of the field.
I actually told someone who was about to enter CMU as a CS undergrad this year “oh, you’ll probably get to take Rudich’s intro class! lucky you!”. I wonder if that was right—was he teaching it this fall?
Comment #8 November 21st, 2024 at 4:30 am
Just read this sad news today. I took 15-251 the spring just before he became completely blind and was sad then about what future classes would miss out on. He really stands out as the most memorable lecturer I have ever had. He would juggle or do magic tricks to make his point, and liven things up with personal anecdotes, sometimes too personal. One that I still remember (feel free to delete or not post publicly if you think this is inappropriate, but he told us) is that he had been making out with his then-novel-love-interest-now-wife when he stopped to ask this law student if she wanted to hear a math problem. Surprisingly she agreed and was presented with the problem we had just discussed in class. She quickly gave the answer (a keeper, clearly) but then was miffed when he asked her to *prove* it. Freshman me could only be in awe of this man, who clearly loved math and cs theory and sharing his love of them with others this much, and could somehow also have a girlfriend.
Comment #9 December 6th, 2024 at 2:46 am
I took Great Theoretical Ideas in Computer Science in 2003. Rudich was the best lecturer I had at CMU, of course. I knew I wasn’t going to study any of the things he was interested in (I was a type theory and PL guy) so we didn’t interact much, but I remember him tell us undergrads about some proof or other that he’d done, which he conceptualized as rabbits emerging from a burrow and hopping on a seesaw — I think there was also an ice cream shop involved? From the way he talked about it it maybe wasn’t one of his more famous results, and Googling around now I can’t figure out what it was, but he was very excited to tell us about it.
Even though I didn’t care about the result at all I still caught that excitement. I think we all did, because we understood what he was really trying to show us: rigor and showmanship don’t have to be enemies. The papers you write don’t have to look like the papers you’ve read. More is possible, and even if you don’t literally put the bunnies in your journal submission you can still think that way, and talk that way, and understand things that way.
And I kept that. I knew from Feynman that that was something great enough scientists could do, but what I got from Rudich was that it was something _I_ could do. And I have.
Comment #10 December 9th, 2024 at 6:47 pm
It is sad to hear he is gone so soon.
I also really enjoyed his paper with Sasha. Definitely one of the lasting papers that will be mentioned 100 years from now.
May he rest is peace.
Comment #11 December 27th, 2024 at 9:35 am
I saw this sad news rather late. Steven was truly sui generis. In addition to being an impactful researcher and once-in-a-generation teacher (he not only won CMU’s teaching awards year after year, he also won national-level teaching awards), he was also a bon vivant and gourmet cook. His health struggles in later years saddened me and also many of his friends and admirers.
Rest in peace, Steven.
Sanjeev Arora