Steven Rudich (born October 4, 1961) is a professor in the
Carnegie Mellon School of Computer Science
The School of Computer Science (SCS) at Carnegie Mellon University in Pittsburgh, Pennsylvania, US is a school for computer science established in 1988. It has been consistently ranked among the top computer science programs over the decades. A ...
. In 1994, he and
Alexander Razborov
Aleksandr Aleksandrovich Razborov (russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is A ...
proved that a large class of combinatorial arguments, dubbed
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 (assuming a widely believed conjecture o ...
s, was unlikely to answer many of the important problems in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
. For this work, they were awarded the
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...
in 2007.
He also co-authored a paper demonstrating that all currently known
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problems remain NP-complete even under AC
0 or NC
0 reductions.
Amongst
Carnegie Mellon
Carnegie may refer to:
People
* Carnegie (surname), including a list of people with the name
* Clan Carnegie, a lowland Scottish clan
Institutions Named for Andrew Carnegie
*Carnegie Building (Troy, New York), on the campus of Rensselaer Polyt ...
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
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. Its editor-in-chief is Vincent Rijmen
Vincent R ...
'', as well as an accomplished
magician
Magician or The Magician may refer to:
Performers
* A practitioner of magic (supernatural)
* A practitioner of magic (illusion)
* Magician (fantasy), a character in a fictional fantasy context
Entertainment
Books
* ''The Magician'', an 18th-ce ...
. His
Erdős number
The Erdős number () describes the "collaborative distance" between mathematician Paul Erdős and another person, as measured by authorship of mathematical papers. The same principle has been applied in other fields where a particular individual ...
is 2.
Oakland.edu
/ref>
Leap@CMU
Rudich (and Merrick Furst, now a Distinguished Professor at the Georgia Institute of Technology
The Georgia Institute of Technology, commonly referred to as Georgia Tech or, in the state of Georgia, as Tech or The Institute, is a public research university and institute of technology in Atlanta, Georgia. Established in 1885, it is part of ...
) 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
External links
Andrew's Leap Homepage
Andrew's Leap Blog
*.
Home page at Carnegie Mellon
{{DEFAULTSORT:Rudich, Steven
American computer scientists
Carnegie Mellon University faculty
1961 births
Living people
Gödel Prize laureates