Steven Rudich, Selected Papers


On The (Im)possibility Of Obfucating Programs

[with B. Barak, O. Goldreich, R. Impagliazzo, A. Sahai, S. Vadhan, K. Yang]


Super-bits, Demi-bits, and NP/poly-natual proofs


Reducing the Complexity of Reductions

[with M. Agrawal, E. Allender, R. Impagliazzo, and T. Pitassi]

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

[with M. Agrawal and E. Allender]

Products and Help Bits in Decision Trees

[with M. Saks and N. Nisan]

Natural Proofs

[with A. Razborov]

The Expressive Power of Voting Polynomials

[with J. Aspnes, R. Biegel, and M. Furst]

Communication Complexity Towards Lower Bounds On Circuit Depth

[with J. Edmonds, R. Impagliazzo, and J. Sgall]

Fast Learning of k-Term DNF Formulas with Queries

[with A. Blum]

Representing Boolean Functions as Polynomials Modulo Composite Numbers

[with R. Beigel and D. Mix Barrington]

Limits on the Provable Consequences of One-Way Permutations

[with R. Impagliazzo]

Ph.D. thesis: Limits on the Provable Consequences of One-way Functions