Computational Complexity: Steven Rudich (1961-2024)
Monday, November 11, 2024
Steven Rudich (1961-2024)
Complexity theorist Steven Rudich passed away on October 29 at the age of 63. His works on Natural Proofs and Program Obfuscation were both highly influential. Russell Impagliazzo had a great result with him on showing that one-way permutations alone isn't enough to get secret key-exchange.<br>I started graduate school in 1985 at Berkeley and Steven was the unofficial student leader of the theory group when I arrived and I got a taste of his optimistic style before I moved to MIT the following summer. I'd see Rudich at various conferences and during visits to each other's institutions. I first learned about natural proofs from a talk he gave at the University of Chicago and we had many debates about its importance for years. Alas health issues took their toll and we lost one of the great researchers and personalities in our field.<br>Impagliazzo has been a friend and colleague of Steven's since they were both undergrads at Wesleyan and we asked him to write a guest post about Steven. Russell sent us a very honest and personal 7-page writeup. Too long for a blog post but I strongly recommend reading this powerful story. Also see Scott Aaronson's memories.
Posted by
Lance Fortnow
at
8:05 AM
Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest
2 comments:
Anonymous1:09 PM, November 11, 2024<br>Russell's write-up is very moving, RIP<br>ReplyDelete<br>Replies<br>Reply
Anonymous8:38 PM, November 11, 2024<br>Very strong and personal write up by Russell. People unfamiliar with the person would not have accepted so many ups and downs for a U.S. born and based academic. V sorry to hear about last years distancing. Sometimes I feel people in our industry don’t have people skills to truly accommodate for rare cases like these.<br>ReplyDelete<br>Replies<br>Reply
Add comment
Load more...
Newer Post
Older Post
Home
Subscribe to:<br>Post Comments (Atom)
Books
Commissions earned from Amazon Links
Mastodon Feed
Blog Links
Bill's Home Page
Lance's Home Page
Favorite Theorems
Foundations of Complexity Lessons
Graduate Student Guide
ChatPNP
CACM P v NP Survey (2009)
CACM Fifty Years of P vs. NP (2022)
CACM Conference Viewpoint
Podcasts
Videos
Posts Feed
Comments Feed
Popular Posts
Tony Hoare (1934-2026)
Respect the P v NP Problem
Two Erdős Problems on Points in the Plane and AI
Humans Solve Erdos Problem!!
Odd Scenarios about Research Claims and Authorships
LEAPing into the Future of Coding
Some thoughts on journals, refereeing, and the P vs NP problem
AI and Intro Theory
mnemonic devices and pangrams that could be real sentences
Authorship in the AI Age
Complexity Links
Complexity Conference
SIGACT
Theory Announcements
Theory Stack Exchange
Complexity Zoo
Complexity on arXiv
Electronic Colloquium on Computational Complexity
Blog Archive
2026
(53)
July
(2)
June
(9)
May
(8)
April
(8)
March
(9)
February
(8)
January
(9)
2025
(98)
December
(6)
November
(8)
October
(9)
September
(8)
August
(8)
July
(9)
June
(9)
May
(8)
April
(8)
March
(9)
February
(6)
January
(10)
2024
(102)
December
(7)
November
(7)
We Will All Write Like AI
For what d is the following true: For all 2-colori...
For what d is the following true: for all 2-colori...
Favorite Theorems: Learning from Natural Proofs
Steven Rudich (1961-2024)
Higher Education Under Trump
A new Mersenne Prime Has Been Found. When will we...