Steven Rudich (October 4, 1961 - October 29, 2024[1]) was a professor in the Carnegie Mellon School of Computer Science. In 1994, he and Alexander Razborov proved that a large class of combinatorial arguments, dubbed natural proofs, was unlikely to answer many of the important problems in computational complexity theory. For this work, they were awarded the Gödel Prize in 2007.[2][3] He also co-authored a paper demonstrating that all currently known NP-complete problems remain NP-complete even under AC0 or NC0 reductions.[4]
Steven Rudich | |
|---|---|
| Born | October 4, 1961 |
| Died | October 29, 2024 (aged 63) |
| Awards | Gödel Prize |
| Academic work | |
| Discipline | Computer Science |
| Sub-discipline | Computational complexity theory |
| Institutions | Carnegie Mellon |
| Notable ideas | Natural proof |
| Website | https://www.cs.cmu.edu/~rudich/ |
Amongst Carnegie Mellon students, he is best known as the teacher of the class "Great Theoretical Ideas in Computer Science" (formerly named "How to Think Like a Computer Scientist"), often considered one of the most difficult classes in the undergraduate computer science curriculum.[citation needed] He was a long-time editor of the Journal of Cryptology,[citation needed] as well as an accomplished magician. His Erdős number is 2.[5]
Leap@CMU
editRudich (and Merrick Furst, now a Distinguished Professor at the Georgia Institute of Technology) began the Leap@CMU (formerly called Andrew's Leap) summer enrichment program for high school (and occasionally, middle school) students in 1991. The summer enrichment program focuses mainly on theoretical aspects of Computer Science in the morning, followed by lunch recess, and then an elective—Robotics, Programming, or Mathematics Theory. The Programming elective is broken down into Intro Programming, Intermediate Programming, and Advanced Programming. As of 2017, the Math Theory Elective has been removed. Most days, there is also an afternoon lecture by a Carnegie Mellon University faculty member. This is placed between lunch and electives.
To enroll in Andrew's Leap, one must take a specialized test known as The Interesting Test. This assessment is supposed to gauge ability to think outside the box, and aptitude for computer-related math. Performance in school is not taken into account when deciding who is ready to take the course.
As of summer 2018, this program has been discontinued.
References
edit- ^ Fortnow, Lance. "Steven Rudich (1961-2024)". Retrieved 2024-11-14.
- ^ "ACM-SIGACT Awards and Prizes: 2007 Gödel Prize". Archived from the original on 2016-03-03. Retrieved 2017-05-22.
- ^ "EATCS: Gödel Prize - 2007". Archived from the original on 2007-12-01.
- ^ Agrawal, M.; Allender, E.; Rudich, Steven (1998). "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem". Journal of Computer and System Sciences. 57 (2). Boston, MA: Academic Press: 127–143. doi:10.1006/jcss.1998.1583. ISSN 1090-2724.
- ^ Oakland.edu
External links
edit- Andrew's Leap Homepage.
- Andrew's Leap Blog.
- Steven Rudich at DBLP Bibliography Server .
- Home page at Carnegie Mellon.
