Steven Rudich
Encyclopedia
Steven Rudich 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 proof
s were unlikely to answer many of the important problems in computational complexity theory
. For this work, they were awarded the Gödel prize
in 2007. He also co-authored a paper demonstrating that all currently known NP-complete
problems remain NP-complete even under AC0 or NC0 reductions.
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. He is an editor of the Journal of Cryptology
, as well as an accomplished magician. His Erdős number is 2.http://www.oakland.edu/enp/thedata/
In order to be enrolled in Andrews' Leap, one must take a specialized test known as The Interesting Test. This assessment gauges one's ability to think outside the box, and one's aptitude for Computer-related math.
Carnegie Mellon School of Computer Science
The School of Computer Science at Carnegie Mellon University in Pittsburgh, Pennsylvania, USA is a leading private school for computer science established in 1965. It has been consistently ranked among the top computer science programs over the decades. U.S...
. In 1994, he and Alexander Razborov
Alexander Razborov
Aleksandr Aleksandrovich Razborov , sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist who won the Nevanlinna Prize in 1990 for introducing the "approximation method" in proving Boolean circuit lower bounds of some essential algorithmic problems, and...
proved that a large class of combinatorial arguments, dubbed natural proof
Natural proof
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown that no such proof can possibly be used to solve the P vs...
s were unlikely to answer many of the important problems in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. For this work, they were awarded the Gödel prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
in 2007. He also co-authored a paper demonstrating that all currently known NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems remain NP-complete even under AC0 or NC0 reductions.
Journal of Cryptology
The Journal of Cryptology is a scientific journal in the field of cryptology and cryptography. The journal is published quarterly by the International Association for Cryptologic Research....
, as well as an accomplished magician. His Erdős number is 2.http://www.oakland.edu/enp/thedata/
Andrews' Leap
Professor Rudich (and Merrick Furst, now a Distinguished Professor at Georgia Tech) began the Andrews' 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 Math Theory. Most days, there is also an afternoon lecture by a Carnegie Mellon University faculty member.In order to be enrolled in Andrews' Leap, one must take a specialized test known as The Interesting Test. This assessment gauges one's ability to think outside the box, and one's aptitude for Computer-related math.