Steven Rudich

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