View source for Steven Rudich

{{short description|American computer scientist (1961–2024)}}
{{Infobox academic
| honorific_prefix = <!-- see [[MOS:CREDENTIAL]] and [[MOS:HONORIFIC]] -->
| name = Steven Rudich
| honorific_suffix = 
| image = Steven Rudich May 2004.jpg
| alt = 
| caption = Rudich in 2004
| birth_date = {{birth date|1961|10|04}}
| birth_place = 
| death_date = {{death date and age|2024|10|29|1961|10|04}}
| death_place = 
| death_cause = 
| region = 
| nationality = 
| citizenship = 
| residence = 
| other_names = 
| occupation = 
| period = 
| known_for = 
| home_town = 
| title = 
| boards = <!--board or similar positions extraneous to main occupation-->
| spouse = 
| partner = 
| children = 
| parents = 
| relatives = 
| awards = [[Gödel Prize]]
| website = https://www.cs.cmu.edu/~rudich/
| education = 
| alma_mater = <!--will often consist of the linked name of the last-attended higher education institution-->
| thesis_title = 
| thesis_url = 
| thesis_year = 
| doctoral_advisor = 
| academic_advisors = 
| influences = <!--must be referenced from a third-party source-->
| discipline = [[Computer Science]]
| sub_discipline = [[Computational complexity theory]]
| workplaces = [[Carnegie Mellon]]
| doctoral_students = <!--only those with WP articles-->
| notable_students = <!--only those with WP articles-->
| main_interests = 
| notable_works = 
| notable_ideas = [[Natural proof]]
| signature = 
| signature_alt = 
| signature_size = 
| footnotes = 
}}

'''Steven Rudich''' ({{IPAc-en|ˈ|r|ʌ|d|ɪ|k}}; October 4, 1961 – October 29, 2024<ref>{{Cite web |last=Fortnow |first=Lance |title=Steven Rudich (1961-2024) |url=https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html |access-date=2024-11-14 |language=en}}</ref>) was an American [[computational theorist]]. He 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 proof]]s, 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.<ref name="razbGodelACM">{{cite web|url=http://www.sigact.org/Prizes/Godel/2007.html|title=ACM-SIGACT Awards and Prizes: 2007 Gödel Prize|access-date=2017-05-22|archive-date=2016-03-03|archive-url=https://web.archive.org/web/20160303173027/http://www.sigact.org/Prizes/Godel/2007.html|url-status=dead}}</ref><ref name="razbGodelEATCS">{{cite web|url=http://eatcs.org/activities/awards/goedel2007.html|title=EATCS: Gödel Prize - 2007|url-status=dead|archive-url=https://web.archive.org/web/20071201092326/http://www.eatcs.org/activities/awards/goedel2007.html|archive-date=2007-12-01}}</ref>  He also co-authored a paper demonstrating that all currently known [[NP-complete]] problems remain NP-complete even under AC<sup>0</sup> or NC<sup>0</sup> reductions.<ref>{{Cite journal | doi=10.1006/jcss.1998.1583 | last1=Agrawal | first1=M. | author1-link=Manindra Agrawal | last2=Allender | first2=E. | last3=Rudich | first3=Steven | title=Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem | publisher=[[Academic Press]] | location=Boston, MA | year=1998 | journal=Journal of Computer and System Sciences | issn=1090-2724 | volume=57 | issue=2 | pages=127–143| doi-access=free }}</ref>

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|date=October 2007}} He was a long-time editor of the ''[[Journal of Cryptology]]'',{{Citation needed|date=January 2013}} as well as an accomplished [[Magician (illusion)|magician]]. His [[List of people by Erdős number|Erdős number]] is 2.<ref>[http://www.oakland.edu/enp/thedata/ Oakland.edu]</ref>

==Leap@CMU==
Rudich (and [[Merrick L. Furst|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==
{{Reflist}}

==External links==
*[https://www.cs.cmu.edu/~leap/ Andrew's Leap Homepage].
*[http://andrewsleap.blogspot.com/ Andrew's Leap Blog].
*{{DBLP |name=Steven Rudich}}.
*[https://www.cs.cmu.edu/~rudich/ Home page at Carnegie Mellon].

{{Gödel winners}}

{{Authority control}}

{{DEFAULTSORT:Rudich, Steven}}
[[Category:American computer scientists]]
[[Category:Carnegie Mellon University faculty]]
[[Category:1961 births]]
[[Category:2024 deaths]]
[[Category:Gödel Prize laureates]]
[[Category:Wesleyan University alumni]]
[[Category:Northfield Mount Hermon School alumni]]
[[Category:Magicians]]