Steven Rudich

2004
35	EE	Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004)
2002
34	EE	Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. FOCS 2002: 197-
2001
33	EE	Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. CRYPTO 2001: 1-18
32	EE	Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the complexity of reductions. Computational Complexity 10(2): 117-138 (2001)
31	EE	Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiri Sgall: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3): 210-246 (2001)
30	EE	Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs Electronic Colloquium on Computational Complexity (ECCC) 8(057): (2001)
1999
29		Noam Nisan, Steven Rudich, Michael E. Saks: Products and Help Bits in Decision Trees. SIAM J. Comput. 28(3): 1035-1050 (1999)
1998
28		Manindra Agrawal, Eric Allender, Steven Rudich: Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. J. Comput. Syst. Sci. 57(2): 127-143 (1998)
1997
27		Steven Rudich: Super-bits, Demi-bits, and NP/qpoly-natural Proofs. RANDOM 1997: 85-93
26	EE	Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the Complexity of Reductions. STOC 1997: 730-738
25		Alexander A. Razborov, Steven Rudich: Natural Proofs. J. Comput. Syst. Sci. 55(1): 24-35 (1997)
1996
24		Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld: The Wakeup Problem. SIAM J. Comput. 25(6): 1331-1332 (1996)
1995
23		Avrim Blum, Steven Rudich: Fast Learning of k-Term DNF Formulas with Queries. J. Comput. Syst. Sci. 51(3): 367-373 (1995)
1994
22		Noam Nisan, Steven Rudich, Michael E. Saks: Products and Help Bits in Decision Trees FOCS 1994: 318-329
21	EE	Alexander A. Razborov, Steven Rudich: Natural proofs. STOC 1994: 204-213
20	EE	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: 253-262
19		James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich: The Expressive Power of Voting Polynomials. Combinatorica 14(2): 135-148 (1994)
18		David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers. Computational Complexity 4: 367-382 (1994)
17	EE	Alexander A. Razborov, Steven Rudich: Natural Proofs Electronic Colloquium on Computational Complexity (ECCC) 1(10): (1994)
1993
16		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): 159-174 (1993)
1992
15		Avrim Blum, Steven Rudich: Fast Learning of k-Term DNF Formulas with Queries STOC 1992: 382-389
14		David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC 1992: 455-461
13		Sampath Kannan, Moni Naor, Steven Rudich: Implicit Representation of Graphs. SIAM J. Discrete Math. 5(4): 596-603 (1992)
1991
12	EE	Steven Rudich: The Use of Interaction in Public Cryptosystems (Extended Abstract). CRYPTO 1991: 242-251
11		Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jiri Sgall: Communication Complexity Towards Lower Bounds on Circuit Depth FOCS 1991: 249-257
10		James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich: The Expressive Power of Voting Polynomials STOC 1991: 402-409
1990
9		Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld: The Wakeup Problem (Extended Abstract) STOC 1990: 106-116
8		Lane A. Hemachandra, Steven Rudich: On the Complexity of Ranking. J. Comput. Syst. Sci. 41(2): 251-271 (1990)
1989
7		David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir: On Dice and Coins: Models of Computation for Random Generation. ICALP 1989: 319-340
6		Russell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: 44-61
1988
5	EE	Russell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-way Permutations. CRYPTO 1988: 8-26
4		Steven Rudich, Leonard Berman: Optimal Circuits and Transitive Automorphism Groups. ICALP 1988: 516-524
3		Sampath Kannan, Moni Naor, Steven Rudich: Implicit Representation of Graphs STOC 1988: 334-343
1985
2		Steven Rudich: Inferring the Structure of a Markov Chain from its Output FOCS 1985: 321-326
1		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: 396-407

Coauthor Index

1	Manindra Agrawal	[26] [28] [32]
2	Eric Allender	[26] [28] [32]
3	Noga Alon	[34] [35]
4	James Aspnes	[10] [19]
5	Boaz Barak	[30] [33]
6	David A. Mix Barrington	[14] [18]
7	Richard Beigel	[10] [14] [18] [19] [34] [35]
8	Leonard Berman	[4]
9	Avrim Blum	[15] [20] [23]
10	Benny Chor	[1]
11	Jeff Edmonds	[11] [31]
12	David Feldman	[7] [16]
13	Michael J. Fischer	[9] [24]
14	Joel Friedman	[1]
15	Merrick L. Furst	[10] [19] [20]
16	Oded Goldreich	[1] [30] [33]
17	Johan Håstad	[1]
18	Lane A. Hemaspaandra (Lane A. Hemachandra)	[8]
19	Russell Impagliazzo	[5] [6] [7] [11] [16] [26] [30] [31] [32] [33]
20	Jeffrey C. Jackson	[20]
21	Sampath Kannan	[3] [13]
22	Simon Kasif	[34] [35]
23	Michael J. Kearns	[20]
24	Yishay Mansour	[20]
25	Shlomo Moran	[9] [24]
26	Moni Naor	[3] [7] [13] [16]
27	Noam Nisan	[7] [16] [22] [29]
28	Toniann Pitassi	[26] [32]
29	Alexander A. Razborov	[17] [21] [25]
30	Amit Sahai	[30] [33]
31	Michael E. Saks	[22] [29]
32	Jiri Sgall	[11] [31]
33	Adi Shamir	[7] [16]
34	Roman Smolensky	[1]
35	Benny Sudakov	[34] [35]
36	Gadi Taubenfeld	[9] [24]
37	Salil P. Vadhan	[30] [33]
38	Ke Yang	[30] [33]

Colors in the list of coauthors