dblp.uni-trier.dewww.uni-trier.de

Steven Rudich Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2004
35EENoga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004)
2002
34EENoga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. FOCS 2002: 197-
2001
33EEBoaz 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
32EEManindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the complexity of reductions. Computational Complexity 10(2): 117-138 (2001)
31EEJeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiri Sgall: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3): 210-246 (2001)
30EEBoaz 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
26EEManindra 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
21EEAlexander A. Razborov, Steven Rudich: Natural proofs. STOC 1994: 204-213
20EEAvrim 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)
17EEAlexander 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
12EESteven 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
7EEDavid 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
5EERussell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-way Permutations. CRYPTO 1988: 8-26
4EESteven 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

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)