Follow
Steven Rudich
Steven Rudich
Professor of Computer Science, Carnegie Mellon University
Verified email at cmu.edu
Title
Cited by
Cited by
Year
On the (im) possibility of obfuscating programs
B Barak, O Goldreich, R Impagliazzo, S Rudich, A Sahai, S Vadhan, ...
Annual international cryptology conference, 1-18, 2001
19302001
Limits on the provable consequences of one-way permutations
R Impagliazzo, S Rudich
Proceedings of the twenty-first annual ACM symposium on Theory of computing …, 1989
8401989
Natural proofs
AA Razborov, S Rudich
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994
7581994
The bit extraction problem or t-resilient functions
B Chor, O Goldreich, J Hasted, J Freidmann, S Rudich, R Smolensky
26th Annual Symposium on Foundations of Computer Science (sfcs 1985), 396-407, 1985
5501985
On the (im) possibility of obfuscating programs
B Barak, O Goldreich, R Impagliazzo, S Rudich, A Sahai, S Vadhan, ...
Journal of the ACM (JACM) 59 (2), 1-48, 2012
5472012
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
A Blum, M Furst, J Jackson, M Kearns, Y Mansour, S Rudich
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994
3441994
Implicit representation of graphs
S Kannan, M Naor, S Rudich
Proceedings of the twentieth annual ACM symposium on Theory of computing …, 1988
3431988
The expressive power of voting polynomials
J Aspnes, R Beigel, M Furst, S Rudich
Proceedings of the twenty-third annual ACM symposium on Theory of Computing …, 1991
2711991
Representing Boolean functions as polynomials modulo composite numbers
DAM Barrington, R Beigel, S Rudich
Computational Complexity 4 (4), 367-382, 1994
1221994
Learning a hidden matching
N Alon, R Beigel, S Kasif, S Rudich, B Sudakov
SIAM Journal on Computing 33 (2), 487-501, 2004
1122004
Limits on the provable consequences of one-way functions
S Rudich
University of California at Berkeley, 1988
1031988
Fast learning of k-term DNF formulas with queries
A Blum, S Rudich
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing …, 1992
1021992
Communication complexity towards lower bounds on circuit depth
J Edmonds, R Impagliazzo, S Rudich, J Sgall
Computational Complexity 10 (3), 210-246, 2001
852001
Computational complexity theory
S Rudich, A Wigderson
American Mathematical Soc., 2004
662004
On the complexity of ranking
LA Hemachandra, S Rudich
Journal of Computer and System Sciences 41 (2), 251-271, 1990
621990
Reductions in circuit complexity: An isomorphism theorem and a gap theorem
M Agrawal, E Allender, S Rudich
Journal of Computer and System Sciences 57 (2), 127-143, 1998
601998
The Use of Interaction in Public Cryptosystems. extended abstract
S Rudich
Annual International Cryptology Conference, 242-251, 1991
591991
Reducing the complexity of reductions
M Agrawal, E Allender, R Impagliazzo, T Pitassi, S Rudich
Computational Complexity 10 (2), 117-138, 2001
532001
Super-bits, demi-bits, and NP/qpoly-natural proofs
S Rudich
International Workshop on Randomization and Approximation Techniques in …, 1997
521997
Inferring the structure of a Markov chain from its output
S Rudich
26th Annual Symposium on Foundations of Computer Science (sfcs 1985), 321-326, 1985
361985
The system can't perform the operation now. Try again later.
Articles 1–20