Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Steven Rudich
Steven Rudich | |
|---|---|
| Born | October 4, 1961 |
| 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/ |
Steven Rudich (born October 4, 1961) is 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.[1][2] He also co-authored a paper demonstrating that all currently known NP-complete problems remain NP-complete even under AC0 or NC0 reductions.[3]
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 is an editor of the Journal of Cryptology,[citation needed] as well as an accomplished magician. His Erdős number is 2.[4]
- ^ "ACM-SIGACT Awards and Prizes: 2007 Gödel Prize".
- ^ "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
Previous Page Next Page
