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

Complexity theory: From Gödel to Feynman.

Steven Rudich

Proceedings of the Computational Complexity Theory., 2004

2002

Learning a Hidden Matching.

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

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

On the (Im)possibility of Obfuscating Programs.

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

Proceedings of the Advances in Cryptology, 2001

1998

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

Manindra Agrawal, Eric Allender, Steven Rudich

J. Comput. Syst. Sci., 1998

1997

Reducing the Complexity of Reductions.

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

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 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

1994

Representing Boolean Functions as Polynomials Modulo Composite Numbers.

David A. Mix Barrington, Richard Beigel, Steven Rudich

Comput. Complex., 1994

Natural proofs.

Alexander A. Razborov, Steven Rudich

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 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

Products and Help Bits in Decision Trees

Noam Nisan, Steven Rudich, Michael E. Saks

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992

Fast Learning of k-Term DNF Formulas with Queries

Avrim Blum, Steven Rudich

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 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 Expressive Power of Voting Polynomials

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

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Communication Complexity Towards Lower Bounds on Circuit Depth

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

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 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

On Dice and Coins: Models of Computation for Random Generation.

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

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988

Implicit Representation of Graphs

Sampath Kannan, Moni Naor, Steven Rudich

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 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