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
19022001
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
8141989
Natural proofs
AA Razborov, S Rudich
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994
7391994
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
5471985
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
5322012
Implicit representation of graphs
S Kannan, M Naor, S Rudich
Proceedings of the twentieth annual ACM symposium on Theory of computing …, 1988
3361988
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
3341994
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
2671991
Representing Boolean functions as polynomials modulo composite numbers
DAM Barrington, R Beigel, S Rudich
Computational Complexity 4, 367-382, 1994
1191994
Learning a hidden matching
N Alon, R Beigel, S Kasif, S Rudich, B Sudakov
SIAM Journal on Computing 33 (2), 487-501, 2004
1082004
Limitson the Provable Consequences of One-way Functions.
S Rudich
1011988
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
971992
Communication complexity towards lower bounds on circuit depth
J Edmonds, R Impagliazzo, S Rudich, J Sgall
Computational Complexity 10, 210-246, 2001
882001
Computational complexity theory
S Rudich, A Wigderson
American Mathematical Soc., 2004
632004
On the complexity of ranking
LA Hemachandra, S Rudich
Journal of Computer and System Sciences 41 (2), 251-271, 1990
631990
The Use of Interaction in Public Cryptosystems. extended abstract
S Rudich
Annual International Cryptology Conference, 242-251, 1991
581991
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
571998
Super-bits, demi-bits, and NP/qpoly-natural proofs
S Rudich
International Workshop on Randomization and Approximation Techniques in …, 1997
541997
Reducing the complexity of reductions
M Agrawal, E Allender, R Impagliazzo, T Pitassi, S Rudich
Computational Complexity 10, 117-138, 2001
492001
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
351985
The system can't perform the operation now. Try again later.
Articles 1–20