Steven Rudich

According to our database, Steven Rudich authored at least 25 papers between 1985 and 2004.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2004

Learning a Hidden Matching.

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov

SIAM J. Comput., 2004

Complexity theory: From Gödel to Feynman.

Steven Rudich

Proceedings of the Computational Complexity Theory., 2004

2001

On the (Im)possibility of Obfuscating Programs

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang

Electron. Colloquium Comput. Complex., 2001

Communication complexity towards lower bounds on circuit depth.

Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jirí Sgall

Comput. Complex., 2001

Reducing the complexity of reductions.

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

Comput. Complex., 2001

1999

Products and Help Bits in Decision Trees.

Noam Nisan, Steven Rudich, Michael E. Saks

SIAM J. Comput., 1999

1998

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.

Manindra Agrawal, Eric Allender, Steven Rudich

J. Comput. Syst. Sci., 1998

1997

Natural Proofs.

Alexander A. Razborov, Steven Rudich

J. Comput. Syst. Sci., 1997

Super-bits, Demi-bits, and NP/qpoly-natural Proofs.

Steven Rudich

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

1996

The future of computational complexity theory: part II.

Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich

SIGACT News, 1996

The Wakeup Problem.

Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld

SIAM J. Comput., 1996

1995

Fast Learning of k-Term DNF Formulas with Queries.

Avrim Blum, Steven Rudich

J. Comput. Syst. Sci., 1995

1994

The Expressive Power of Voting Polynomials.

James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich

Comb., 1994

Representing Boolean Functions as Polynomials Modulo Composite Numbers.

David A. Mix Barrington, Richard Beigel, Steven Rudich

Comput. Complex., 1994

Weakly learning DNF and characterizing statistical query learning using Fourier analysis.

Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

On Dice and Coins: Models of Computation for Random Generation

David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir

Inf. Comput., June, 1993

1992

Implicit Representation of Graphs.

Sampath Kannan, Moni Naor, Steven Rudich

SIAM J. Discret. Math., 1992

Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)

David A. Mix Barrington, Richard Beigel, Steven Rudich

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

The Use of Interaction in Public Cryptosystems (Extended Abstract).

Steven Rudich

Proceedings of the Advances in Cryptology, 1991

1990

On the Complexity of Ranking.

Lane A. Hemachandra, Steven Rudich

J. Comput. Syst. Sci., 1990

The Wakeup Problem (Extended Abstract)

Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

1989

Limits on the Provable Consequences of One-Way Permutations

Russell Impagliazzo, Steven Rudich

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

Optimal Circuits and Transitive Automorphism Groups.

Steven Rudich, Leonard Berman

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1985

Inferring the Structure of a Markov Chain from its Output

Steven Rudich

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985