Steven Rudich

Steven Rudich's AcademicInfluence.com Rankings

Steven Rudich

Computer Science

#1182

World Rank

#1222

Historical Rank

#611

USA Rank

Theoretical Computer Science

#114

World Rank

#114

Historical Rank

#29

USA Rank

Database

#7224

World Rank

#7473

Historical Rank

#859

USA Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Steven Rudich Influential?

(Suggest an Edit or Addition)

According to Wikipedia, 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 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. He also co-authored a paper demonstrating that all currently known NP-complete problems remain NP-complete even under AC0 or NC0 reductions.

(See a Problem?)

Steven Rudich's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

On the (im)possibility of obfuscating programs (2001) (1429)
Limits on the provable consequences of one-way permutations (1988) (648)
Natural proofs (1994) (585)
The bit extraction problem or t-resilient functions (1985) (370)
Weakly learning DNF and characterizing statistical query learning using Fourier analysis (1994) (279)
Implicit representation of graphs (1992) (259)
The expressive power of voting polynomials (1991) (211)
Representing Boolean functions as polynomials modulo composite numbers (1992) (126)
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) (1985) (122)
Communication complexity towards lower bounds on circuit depth (1991) (88)
Learning a hidden matching (2002) (86)
Limits on the provable consequences of one-way functions (1983) (82)
Fast learning of k-term DNF formulas with queries (1992) (79)
On the (im)possibility of obfuscating programs : (Extended abstract) (2001) (55)
Reducing the complexity of reductions (1997) (53)
The Use of Interaction in Public Cryptosystems (Extended Abstract) (1991) (48)
The wakeup problem (1990) (43)
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem (1998) (43)
Products and help bits in decision trees (1994) (41)
On the Complexity of Ranking (1990) (36)
Computational Complexity Theory (2004) (36)
Super-bits, Demi-bits, and NP/qpoly-natural Proofs (1997) (33)
Inferring the Structure of a Markov Chain from its Output (1985) (33)
On Dice and Coins: Models of Computation for Random Generation (1989) (17)
Cryptography and Computer Security (2003) (13)
Optimal Circuits and Transitive Automorphism Groups (1988) (6)
A On the ( Im ) (2012) (6)
The future of computational complexity theory: part II (1996) (5)
Complexity theory: From Gödel to Feynman (2004) (3)
Learning a Hidden Matching Combinatorial Identification of Hidden Matchings with Applications to (2002) (2)
On the communication complexity of correlation and entanglement distillation (2004) (1)
Mathematical Foundations for Understanding and Designing Conceptualizing Strategizing Control ( CONSCS ) Systems (2004) (1)
Security and privacy in the information economy. (1997) (1)
The Wakeup Problem * • ( DRAFT ) (2014) (0)
CORACT OR GRANT NUMBE() (1990) (0)
The Wakeup Problem (Extended Abstract) (1990) (0)

This paper list is powered by the following services:

Other Resources About Steven Rudich

en.wikipedia.org

What Schools Are Affiliated With Steven Rudich?

Steven Rudich is affiliated with the following schools:

Carnegie Mellon University

Steven Rudich's Academic­Influence.com Rankings

Why Is Steven Rudich Influential?

Steven Rudich's Published Works

Published Works

Other Resources About Steven Rudich

What Schools Are Affiliated With Steven Rudich?

Steven Rudich's AcademicInfluence.com Rankings