Steven Rudich

Publication Activity (10 Years)

Years Active: 1985-2012
Publications (10 Years): 0

Top Topics

Provably Correct

Control Program

Top Venues

Publications

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
On the (im)possibility of obfuscating programs. J. ACM 59 (2) (2012)
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
Learning a Hidden Matching. SIAM J. Comput. 33 (2) (2004)
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
Learning a Hidden Matching. FOCS (2002)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
On the (Im)possibility of Obfuscating Programs. IACR Cryptol. ePrint Arch. 2001 (2001)
Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jirí Sgall
Communication complexity towards lower bounds on circuit depth. Comput. Complex. 10 (3) (2001)
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
Reducing the complexity of reductions. Comput. Complex. 10 (2) (2001)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
On the (Im)possibility of Obfuscating Programs Electron. Colloquium Comput. Complex. 8 (057) (2001)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
On the (Im)possibility of Obfuscating Programs. CRYPTO (2001)
Noam Nisan, Steven Rudich, Michael E. Saks
Products and Help Bits in Decision Trees. SIAM J. Comput. 28 (3) (1999)
Manindra Agrawal, Eric Allender, Steven Rudich
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. J. Comput. Syst. Sci. 57 (2) (1998)
Alexander A. Razborov, Steven Rudich
Natural Proofs. J. Comput. Syst. Sci. 55 (1) (1997)
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
Reducing the Complexity of Reductions. STOC (1997)
Steven Rudich
Super-bits, Demi-bits, and NP/qpoly-natural Proofs. RANDOM (1997)
Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich
The future of computational complexity theory: part II. SIGACT News 27 (4) (1996)
Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld
The Wakeup Problem. SIAM J. Comput. 25 (6) (1996)
Avrim Blum, Steven Rudich
Fast Learning of k-Term DNF Formulas with Queries. J. Comput. Syst. Sci. 51 (3) (1995)
Alexander A. Razborov, Steven Rudich
Natural proofs. STOC (1994)
David A. Mix Barrington, Richard Beigel, Steven Rudich
Representing Boolean Functions as Polynomials Modulo Composite Numbers. Comput. Complex. 4 (1994)
Noam Nisan, Steven Rudich, Michael E. Saks
Products and Help Bits in Decision Trees FOCS (1994)
Alexander A. Razborov, Steven Rudich
Natural Proofs Electron. Colloquium Comput. Complex. 1 (10) (1994)
Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich
Weakly learning DNF and characterizing statistical query learning using Fourier analysis. STOC (1994)
James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich
The Expressive Power of Voting Polynomials. Comb. 14 (2) (1994)
David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir
On Dice and Coins: Models of Computation for Random Generation Inf. Comput. 104 (2) (1993)
Avrim Blum, Steven Rudich
Fast Learning of k-Term DNF Formulas with Queries STOC (1992)
David A. Mix Barrington, Richard Beigel, Steven Rudich
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC (1992)
Sampath Kannan, Moni Naor, Steven Rudich
Implicit Representation of Graphs. SIAM J. Discret. Math. 5 (4) (1992)
James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich
The Expressive Power of Voting Polynomials STOC (1991)
Steven Rudich
The Use of Interaction in Public Cryptosystems (Extended Abstract). CRYPTO (1991)
Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jirí Sgall
Communication Complexity Towards Lower Bounds on Circuit Depth FOCS (1991)
Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld
The Wakeup Problem (Extended Abstract) STOC (1990)
Lane A. Hemachandra, Steven Rudich
On the Complexity of Ranking. J. Comput. Syst. Sci. 41 (2) (1990)
Russell Impagliazzo, Steven Rudich
Limits on the Provable Consequences of One-Way Permutations STOC (1989)
David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir
On Dice and Coins: Models of Computation for Random Generation. ICALP (1989)
Sampath Kannan, Moni Naor, Steven Rudich
Implicit Representation of Graphs STOC (1988)
Russell Impagliazzo, Steven Rudich
Limits on the Provable Consequences of One-way Permutations. CRYPTO (1988)
Steven Rudich, Leonard Berman
Optimal Circuits and Transitive Automorphism Groups. ICALP (1988)
Steven Rudich
Inferring the Structure of a Markov Chain from its Output FOCS (1985)
Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) FOCS (1985)