Russell Impagliazzo

	2012
148		Russell Impagliazzo, William Matthews, Ramamohan Paturi: A satisfiability algorithm for AC0. SODA 2012: 961-972
147		Paul Beame, Christopher Beck, Russell Impagliazzo: Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC 2012: 213-232
146		Russell Impagliazzo, Cristopher Moore, Alexander Russell: An Entropic Proof of Chang's Inequality CoRR abs/1205.0263: (2012)
145		Chris Beck, Russell Impagliazzo, Shachar Lovett: Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Electronic Colloquium on Computational Complexity (ECCC) 19: 42 (2012)
144		Russell Impagliazzo, Raghu Meka, David Zuckerman: Pseudorandomness from Shrinkage. Electronic Colloquium on Computational Complexity (ECCC) 19: 57 (2012)
143		Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (im)possibility of obfuscating programs. J. ACM 59(2): 6 (2012)
	2011
142		Russell Impagliazzo: Relativized Separations of Worst-Case and Average-Case Complexities for NP. IEEE Conference on Computational Complexity 2011: 104-114
141		Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo: A Stronger Model of Dynamic Programming Algorithms. Algorithmica 60(4): 938-968 (2011)
140		Russell Impagliazzo, William Matthews, Ramamohan Paturi: A Satisfiability Algorithm for AC$^0$ CoRR abs/1107.3127: (2011)
139		Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. Computational Complexity 20(4): 679-740 (2011)
138		Paul Beame, Chris Beck, Russell Impagliazzo: Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electronic Colloquium on Computational Complexity (ECCC) 18: 149 (2011)
	2010
137		Russell Impagliazzo, Valentine Kabanets: Constructive Proofs of Concentration Bounds. APPROX-RANDOM 2010: 617-631
136		Russell Impagliazzo, Ryan Williams: Communication Complexity with Synchronized Clocks. IEEE Conference on Computational Complexity 2010: 259-269
135		Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: On the Exact Complexity of Evaluating Quantified k-CNF. IPEC 2010: 50-59
134		Eli Ben-Sasson, Russell Impagliazzo: Random Cnf's are Hard for the Polynomial Calculus. Computational Complexity 19(4): 501-519 (2010)
133		Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer: Improved Algorithms for Unique Games via Divide and Conquer. Electronic Colloquium on Computational Complexity (ECCC) 17: 41 (2010)
132		Russell Impagliazzo, Valentine Kabanets: Constructive Proofs of Concentration Bounds. Electronic Colloquium on Computational Complexity (ECCC) 17: 72 (2010)
131		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637-1665 (2010)
130		Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. TOCT 1(3): (2010)
	2009
129		Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: The Complexity of Satisfiability of Small Depth Circuits. IWPEC 2009: 75-85
128		Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New direct-product testers and 2-query PCPs. STOC 2009: 131-140
127		Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova: An axiomatic approach to algebrization. STOC 2009: 695-704
126		Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Security Amplification for InteractiveCryptographic Primitives. TCC 2009: 128-145
125		Sashka Davis, Russell Impagliazzo: Models of Greedy Algorithms for Graph Problems. Algorithmica 54(3): 269-317 (2009)
124		Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen: Toward a Model for Backtracking and Dynamic Programming. Electronic Colloquium on Computational Complexity (ECCC) 16: 38 (2009)
123		Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New Direct-Product Testers and 2-Query PCPs. Electronic Colloquium on Computational Complexity (ECCC) 16: 90 (2009)
122		Russell Impagliazzo, Philippe Moser: A zero-one law for RP and derandomization of AM if NP is not small. Inf. Comput. 207(7): 787-792 (2009)
121		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Chernoff-Type Direct Product Theorems. J. Cryptology 22(1): 75-92 (2009)
120		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput. 39(2): 564-605 (2009)
	2008
119		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588
118		Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353-376 (2008)
117		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electronic Colloquium on Computational Complexity (ECCC) 15(079): (2008)
116		Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi: The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. J. Comput. Syst. Sci. 74(3): 386-393 (2008)
	2007
115		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Chernoff-Type Direct Product Theorems. CRYPTO 2007: 500-516
114		Paul Beame, Russell Impagliazzo, Ashish Sabharwal: The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Computational Complexity 16(3): 245-297 (2007)
	2006
113		Sashka Davis, Jeff Edmonds, Russell Impagliazzo: Online Algorithms to Minimize Resource Reallocations and Network Communication. APPROX-RANDOM 2006: 104-115
112		Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. FOCS 2006: 187-196
111		Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: A Duality between Clause Width and Clause Density for SAT. IEEE Conference on Computational Complexity 2006: 252-260
110		Russell Impagliazzo: Can every randomized algorithm be derandomized? STOC 2006: 373-374
109		Russell Impagliazzo, Nathan Segerlind: Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. 7(2): 199-218 (2006)
108		Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Reducing The Seed Length In The Nisan-Wigderson Generator. Combinatorica 26(6): 647-681 (2006)
107		Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel: Infinitely-Often Universal Languages and Diagonalization. Electronic Colloquium on Computational Complexity (ECCC) 13(051): (2006)
106		Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. Electronic Colloquium on Computational Complexity (ECCC) 13(140): (2006)
105		Russell Impagliazzo, Bruce M. Kapron: Logics for reasoning about cryptographic constructions. J. Comput. Syst. Sci. 72(2): 286-320 (2006)
104		Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006)
	2005
103		Russell Impagliazzo: Computational Complexity Since 1980. FSTTCS 2005: 19-47
102		Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. IEEE Conference on Computational Complexity 2005: 308-322
101		Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. IEEE Conference on Computational Complexity 2005: 323-332
100		Sashka Davis, Russell Impagliazzo: Models of Greedy Algorithms for Graph Problems Electronic Colloquium on Computational Complexity (ECCC)(120): (2005)
	2004
99		Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393
98		Sashka Davis, Russell Impagliazzo: Models of greedy algorithms for graph problems. SODA 2004: 381-390
97		Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near Optimal Separation Of Tree-Like And General Resolution. Combinatorica 24(4): 585-603 (2004)
96		Valentine Kabanets, Russell Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1-2): 1-46 (2004)
95		Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the complexity of succinct zero-sum games Electronic Colloquium on Computational Complexity (ECCC)(001): (2004)
94		Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution. SIAM J. Comput. 33(5): 1171-1200 (2004)
	2003
93		Russell Impagliazzo, Bruce M. Kapron: Logics for Reasoning about Cryptographic Constructions. FOCS 2003: 372-383
92		Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi: The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. IEEE Conference on Computational Complexity 2003: 135-
91		Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Memoization and DPLL: Formula Caching Proof Systems. IEEE Conference on Computational Complexity 2003: 248-
90		Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel: Universal Languages and the Power of Diagonalization. IEEE Conference on Computational Complexity 2003: 337-346
89		Russell Impagliazzo, Philippe Moser: A zero one law for RP. IEEE Conference on Computational Complexity 2003: 48-52
88		Valentine Kabanets, Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. STOC 2003: 355-364
87		Russell Impagliazzo, Sara Miner More: Anonymous credentials with biometrically-enforced non-transferability. WPES 2003: 60-71
86		Russell Impagliazzo: Hardness as randomness: a survey of universal derandomization CoRR cs.CC/0304040: (2003)
85		Russell Impagliazzo, Nathan Segerlind: Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations CoRR cs.CC/0308012: (2003)
	2002
84		Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS 2002: 604-
83		Russell Impagliazzo, Nathan Segerlind: Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. ICALP 2002: 208-219
82		Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi: Homogenization and the polynomial calculus. Computational Complexity 11(3-4): 91-108 (2002)
81		Valentine Kabanets, Russell Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds Electronic Colloquium on Computational Complexity (ECCC)(055): (2002)
80		Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. 65(4): 672-694 (2002)
79		Russell Impagliazzo, Jan Krajícek: A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. 48(3): 375-377 (2002)
	2001
78		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
77		Russell Impagliazzo, Nathan Segerlind: Counting Axioms Do Not Polynomially Simulate Counting Gates. FOCS 2001: 200-209
76		Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. IEEE Conference on Computational Complexity 2001: 2-12
75		Paul Beame, Russell Impagliazzo, Ashish Sabharwal: Resolution Complexity of Independent Sets in Random Graphs. IEEE Conference on Computational Complexity 2001: 52-68
74		Russell Impagliazzo: Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. RANDOM-APPROX 2001: 2-5
73		Ted Carson, Russell Impagliazzo: Hill-climbing finds random planted bisections. SODA 2001: 903-909
72		Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the complexity of reductions. Computational Complexity 10(2): 117-138 (2001)
71		Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiri Sgall: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3): 210-246 (2001)
70		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)
69		Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. IACR Cryptology ePrint Archive 2001: 69 (2001)
68		Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62(2): 267-289 (2001)
67		Russell Impagliazzo, Ramamohan Paturi: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2): 367-375 (2001)
66		Russell Impagliazzo, Ramamohan Paturi, Francis Zane: Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. 63(4): 512-530 (2001)
65		Russell Impagliazzo, Avi Wigderson: Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci. 63(4): 672-688 (2001)
	2000
64		Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi: Homogenization and the Polynominal Calculus. ICALP 2000: 926-937
63		Pavel Pudlák, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136
62		Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. STOC 2000: 1-10
61		Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near-Optimal Separation of Treelike and General Resolution Electronic Colloquium on Computational Complexity (ECCC) 7(5): (2000)
60		Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length Electronic Colloquium on Computational Complexity (ECCC) 7(9): (2000)
	1999
59		Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS 1999: 181-190
58		Eli Ben-Sasson, Russell Impagliazzo: Random CNF's are Hard for the Polynomial Calculus. FOCS 1999: 415-421
57		Russell Impagliazzo, Ramamohan Paturi: Complexity of k-SAT. IEEE Conference on Computational Complexity 1999: 237-240
56		Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). IEEE Conference on Computational Complexity 1999: 5
55		Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson: How to Forget a Secret. STACS 1999: 500-509
54		Giovanni Di Crescenzo, Russell Impagliazzo: Security-Preserving Hardness-Amplification for Any Regular One-Way Function. STOC 1999: 169-178
53		Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556
52		Russell Impagliazzo, Pavel Pudlák, Jiri Sgall: Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Computational Complexity 8(2): 127-144 (1999)
51		Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby: A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4): 1364-1396 (1999)
	1998
50		Russell Impagliazzo, Ramamohan Paturi, Francis Zane: Which Problems Have Strongly Exponential Complexity? FOCS 1998: 653-663
49		Russell Impagliazzo, Avi Wigderson: Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS 1998: 734-743
48		Giovanni Di Crescenzo, Russell Impagliazzo: Proofs of Membership vs. Proofs of Knowledge. IEEE Conference on Computational Complexity 1998: 34-45
47		Tassos Dimitriou, Russell Impagliazzo: Go with the Winners for Graph Bisection. SODA 1998: 510-520
46		Paul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Bounds for Small Distance Connectivity. Computational Complexity 7(4): 325-345 (1998)
45		Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. 57(1): 3-19 (1998)
	1997
44		Mihir Bellare, Russell Impagliazzo, Moni Naor: Does Parallel Repetition Lower the Error in Computationally Sound Protocols? FOCS 1997: 374-383
43		Russell Impagliazzo: Using Hard Problems to Derandomize Algorithms: An Incomplete Survey. RANDOM 1997: 165-173
42		Russell Impagliazzo, Avi Wigderson: P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. STOC 1997: 220-229
41		Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the Complexity of Reductions. STOC 1997: 730-738
40		Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Computational Complexity 6(3): 256-298 (1997)
39		Russell Impagliazzo, Pavel Pudlák, Jiri Sgall: Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm Electronic Colloquium on Computational Complexity (ECCC) 4(42): (1997)
38		Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami: A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory. Inf. Comput. 137(2): 159-170 (1997)
37		Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks: Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. 26(3): 693-707 (1997)
36		Arvind Gupta, Russell Impagliazzo: Bounding the Size of Planar Intertwines. SIAM J. Discrete Math. 10(3): 337-358 (1997)
	1996
35		Markus Jakobsson, Kazue Sako, Russell Impagliazzo: Designated Verifier Proofs and Their Applications. EUROCRYPT 1996: 143-154
34		Matthew Clegg, Jeff Edmonds, Russell Impagliazzo: Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. STOC 1996: 174-183
33		Tassos Dimitriou, Russell Impagliazzo: Towards an Analysis of Local Optimization Algorithms. STOC 1996: 304-313
32		Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski: Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. J. Comput. Syst. Sci. 53(1): 104-111 (1996)
31		Russell Impagliazzo, Moni Naor: Efficient Cryptographic Schemes Provably as Secure as Subset Sum. J. Cryptology 9(4): 199-216 (1996)
	1995
30		Russell Impagliazzo: Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995: 538-545
29		Paul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Vounds for Small Distance Connectivity. FOCS 1995: 692-701
28		Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The relative complexity of NP search problems. STOC 1995: 303-314
27		Russell Impagliazzo: A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147
26		Andrea E. F. Clementi, Russell Impagliazzo: The Reachability Problem for Finite Cellular Automata. Inf. Process. Lett. 53(1): 27-31 (1995)
	1994
25		Andrea E. F. Clementi, Russell Impagliazzo: Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata. CIAC 1994: 73-90
24		Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák: Lower Bound on Hilbert's Nullstellensatz and propositional proofs FOCS 1994: 794-806
23		Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart: Upper and Lower Bounds for Tree-Like Cutting Planes Proofs LICS 1994: 220-228
22		Russell Impagliazzo, Noam Nisan, Avi Wigderson: Pseudorandomness for network algorithms. STOC 1994: 356-364
21		Russell Impagliazzo, Ran Raz, Avi Wigderson: A Direct Product Theorem. Structure in Complexity Theory Conference 1994: 88-96
	1993
20		Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski: Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. STACS 1993: 386-397
19		Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks: Size-depth trade-offs for threshold circuits. STOC 1993: 541-550
18		Toniann Pitassi, Paul Beame, Russell Impagliazzo: Exponential Lower Bounds for the Pigeonhole Principle. Computational Complexity 3: 97-140 (1993)
17		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)
16		Russell Impagliazzo, Noam Nisan: The Effect of Random Restrictions on Formula Size. Random Struct. Algorithms 4(2): 121-134 (1993)
	1992
15		Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods: Exponential Lower Bounds for the Pigeonhole Principle STOC 1992: 200-220
	1991
14		Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jiri Sgall: Communication Complexity Towards Lower Bounds on Circuit Depth FOCS 1991: 249-257
13		Arvind Gupta, Russell Impagliazzo: Computing Planar Intertwines FOCS 1991: 802-811
	1990
12		Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman: Security Preserving Amplification of Hardness FOCS 1990: 318-326
11		Russell Impagliazzo, Leonid A. Levin: No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random FOCS 1990: 812-821
	1989
10		Russell Impagliazzo, Gábor Tardos: Decision Versus Search Problems in Super-Polynomial Time FOCS 1989: 222-227
9		Russell Impagliazzo, Michael Luby: One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract) FOCS 1989: 230-235
8		Russell Impagliazzo, Moni Naor: Efficient Cryptographic Schemes Provably as Secure as Subset Sum FOCS 1989: 236-241
7		Russell Impagliazzo, David Zuckerman: How to Recycle Random Bits FOCS 1989: 248-253
6		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
5		Russell Impagliazzo, Leonid A. Levin, Michael Luby: Pseudo-random Generation from one-way functions (Extended Abstracts) STOC 1989: 12-24
4		Russell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: 44-61
	1988
3		Russell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-way Permutations. CRYPTO 1988: 8-26
	1987
2		Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51
1		Manuel Blum, Russell Impagliazzo: Generic Oracles and Oracle Classes (Extended Abstract) FOCS 1987: 118-126

Coauthor Index

1	Manindra Agrawal	[41] [72]
2	Michael Alekhnovich	[102] [124] [139]
3	Eric Allender	[41] [72]
4	Sanjeev Arora	[133]
5	Boaz Barak	[69] [70] [78] [99] [104] [143]
6	Paul Beame	[15] [18] [24] [28] [29] [45] [46] [75] [91] [106] [114] [130] [138] [147]
7	Chris Beck (Christopher Beck)	[138] [145] [147]
8	Mihir Bellare	[44]
9	Eli Ben-Sasson	[58] [61] [97] [134]
10	Manuel Blum	[1]
11	Allan Borodin	[102] [124] [139]
12	Joshua Buresh-Oppenheim (Josh Buresh-Oppenheim)	[64] [82] [102] [124] [139] [141]
13	Samuel R. Buss	[40] [53] [56] [68] [84] [94]
14	Chris Calabro	[92] [111] [116] [129] [135]
15	Ted Carson	[73]
16	Matthew Clegg	[34] [64] [82]
17	Andrea E. F. Clementi	[25] [26]
18	Stephen A. Cook	[28] [38] [45]
19	Giovanni Di Crescenzo	[48] [54] [55]
20	Sashka Davis	[98] [100] [113] [125] [141]
21	Tassos Dimitriou	[33] [47]
22	Yevgeniy Dodis	[126]
23	Jeff Edmonds	[14] [28] [34] [45] [71] [113]
24	Faith Ellen (Faith Ellen Fich, Faith E. Fich)	[20] [32]
25	David Feldman	[6] [17]
26	Niels Ferguson	[55]
27	Lance Fortnow	[95] [101] [118]
28	Oded Goldreich	[12] [69] [70] [78] [143]
29	Dima Grigoriev	[53] [56] [68]
30	Arvind Gupta	[13] [36]
31	Johan Håstad	[51]
32	Ragesh Jaiswal	[112] [115] [117] [119] [120] [121] [126] [131]
33	Markus Jakobsson	[35] [55]
34	Valentine Kabanets	[76] [80] [81] [88] [92] [95] [96] [101] [112] [115] [116] [117] [118] [119] [120] [121] [123] [126] [127] [128] [131] [132] [137]
35	Bruce M. Kapron	[20] [32] [93] [105]
36	Valerie King	[20] [32]
37	Antonina Kolokolova	[127]
38	Jan Krajícek	[15] [24] [40] [79]
39	Miroslaw Kutylowski	[20] [32]
40	Leonid A. Levin	[5] [11] [12] [51]
41	Shachar Lovett	[145]
42	Michael Luby	[5] [9] [51]
43	Avner Magen	[102] [124] [139]
44	William Matthews	[133] [140] [148]
45	Raghu Meka	[144]
46	Cristopher Moore	[146]
47	Sara Miner More (Sara K. Miner)	[87]
48	Philippe Moser	[89] [122]
49	Moni Naor	[6] [8] [17] [31] [44]
50	Alan Nash	[90] [107]
51	Noam Nisan	[6] [16] [17] [22]
52	Ramamohan Paturi	[19] [37] [50] [57] [66] [67] [92] [111] [116] [129] [135] [140] [148]
53	Toniann Pitassi	[15] [18] [23] [24] [28] [29] [41] [45] [46] [53] [56] [64] [68] [72] [82] [91] [102] [106] [130] [139]
54	Pavel Pudlák	[15] [24] [39] [40] [52] [63]
55	Ran Raz	[21]
56	Alexander A. Razborov	[40]
57	Jeffrey B. Remmel	[90] [107]
58	Steven Rudich	[3] [4] [6] [14] [17] [41] [69] [70] [71] [72] [78] [143]
59	Alexander Russell	[146]
60	Ashish Sabharwal	[75] [114]
61	Amit Sahai	[69] [70] [78] [143]
62	Kazue Sako	[35]
63	Michael E. Saks (Michael Saks)	[19] [37]
64	Nathan Segerlind	[77] [83] [84] [85] [91] [94] [106] [109] [130]
65	Jiri Sgall	[14] [39] [40] [52] [71]
66	Ronen Shaltiel	[59] [60] [62] [108]
67	Adi Shamir	[6] [17]
68	David Steurer	[133]
69	Gábor Tardos	[10]
70	Christopher Umans	[95] [101] [118]
71	Alasdair Urquhart	[23]
72	Salil P. Vadhan	[69] [70] [78] [143]
73	Ramarathnam Venkatesan	[12]
74	Avi Wigderson	[21] [22] [42] [49] [59] [60] [61] [62] [65] [76] [80] [97] [99] [104] [108] [117] [119] [123] [128] [131]
75	Ryan Williams (R. Ryan Williams)	[136]
76	Alan R. Woods	[15]
77	Tomoyuki Yamakami	[38]
78	Ke Yang	[69] [70] [78] [143]
79	Moti Yung (Mordechai M. Yung)	[2]
80	Francis Zane	[50] [66]
81	David Zuckerman	[7] [12] [144]

Colors in the list of coauthors

Last update Sat Jun 2 20:57:36 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page