Russell Impagliazzo

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: On the Exact Complexity of Evaluating Quantified k -CNF. Algorithmica 65(4): 817-827 (2013)

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)

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. 41(6): 1722-1768 (2012)

Paul Beame, Russell Impagliazzo, Srikanth Srinivasan: Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. IEEE Conference on Computational Complexity 2012: 117-125

Chris Beck, Russell Impagliazzo, Shachar Lovett: Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. FOCS 2012: 101-110

Russell Impagliazzo, Raghu Meka, David Zuckerman: Pseudorandomness from Shrinkage. FOCS 2012: 111-119

Russell Impagliazzo, William Matthews, Ramamohan Paturi: A satisfiability algorithm for AC⁰. SODA 2012: 961-972

Paul Beame, Christopher Beck, Russell Impagliazzo: Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC 2012: 213-232

Russell Impagliazzo, Cristopher Moore, Alexander Russell: An Entropic Proof of Chang's Inequality. CoRR abs/1205.0263 (2012)

Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider: A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits. CoRR abs/1212.4548 (2012)

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)

Russell Impagliazzo, Raghu Meka, David Zuckerman: Pseudorandomness from Shrinkage. Electronic Colloquium on Computational Complexity (ECCC) 19: 57 (2012)

Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo: A Stronger Model of Dynamic Programming Algorithms. Algorithmica 60(4): 938-968 (2011)

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)

Russell Impagliazzo: Relativized Separations of Worst-Case and Average-Case Complexities for NP. IEEE Conference on Computational Complexity 2011: 104-114

Russell Impagliazzo, William Matthews, Ramamohan Paturi: A Satisfiability Algorithm for AC$^0$. CoRR abs/1107.3127 (2011)

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)

Eli Ben-Sasson, Russell Impagliazzo: Random Cnf's are Hard for the Polynomial Calculus. Computational Complexity 19(4): 501-519 (2010)

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637-1665 (2010)

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. TOCT 1(3) (2010)

Russell Impagliazzo, Valentine Kabanets: Constructive Proofs of Concentration Bounds. APPROX-RANDOM 2010: 617-631

Russell Impagliazzo, Ryan Williams: Communication Complexity with Synchronized Clocks. IEEE Conference on Computational Complexity 2010: 259-269

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: On the Exact Complexity of Evaluating Quantified k-CNF. IPEC 2010: 50-59

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)

Russell Impagliazzo, Valentine Kabanets: Constructive Proofs of Concentration Bounds. Electronic Colloquium on Computational Complexity (ECCC) 17: 72 (2010)

Sashka Davis, Russell Impagliazzo: Models of Greedy Algorithms for Graph Problems. Algorithmica 54(3): 269-317 (2009)

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)

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Chernoff-Type Direct Product Theorems. J. Cryptology 22(1): 75-92 (2009)

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)

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: The Complexity of Satisfiability of Small Depth Circuits. IWPEC 2009: 75-85

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New direct-product testers and 2-query PCPs. STOC 2009: 131-140

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova: An axiomatic approach to algebrization. STOC 2009: 695-704

Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Security Amplification for InteractiveCryptographic Primitives. TCC 2009: 128-145

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)

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New Direct-Product Testers and 2-Query PCPs. Electronic Colloquium on Computational Complexity (ECCC) 16: 90 (2009)

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353-376 (2008)

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)

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588

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)

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)

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Chernoff-Type Direct Product Theorems. CRYPTO 2007: 500-516

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Reducing The Seed Length In The Nisan-Wigderson Generator. Combinatorica 26(6): 647-681 (2006)

Russell Impagliazzo, Bruce M. Kapron: Logics for reasoning about cryptographic constructions. J. Comput. Syst. Sci. 72(2): 286-320 (2006)

Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006)

Russell Impagliazzo, Nathan Segerlind: Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. 7(2): 199-218 (2006)

Sashka Davis, Jeff Edmonds, Russell Impagliazzo: Online Algorithms to Minimize Resource Reallocations and Network Communication. APPROX-RANDOM 2006: 104-115

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi: A Duality between Clause Width and Clause Density for SAT. IEEE Conference on Computational Complexity 2006: 252-260

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets: Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. FOCS 2006: 187-196

Russell Impagliazzo: Can every randomized algorithm be derandomized? STOC 2006: 373-374

Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel: Infinitely-Often Universal Languages and Diagonalization. Electronic Colloquium on Computational Complexity (ECCC) 13(051) (2006)

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. Electronic Colloquium on Computational Complexity (ECCC) 13(140) (2006)

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

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. IEEE Conference on Computational Complexity 2005: 323-332

Russell Impagliazzo: Computational Complexity Since 1980. FSTTCS 2005: 19-47

Sashka Davis, Russell Impagliazzo: Models of Greedy Algorithms for Graph Problems. Electronic Colloquium on Computational Complexity (ECCC)(120) (2005)

Valentine Kabanets, Russell Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1-2): 1-46 (2004)

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near Optimal Separation Of Tree-Like And General Resolution. Combinatorica 24(4): 585-603 (2004)

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)

Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393

Sashka Davis, Russell Impagliazzo: Models of greedy algorithms for graph problems. SODA 2004: 381-390

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the complexity of succinct zero-sum games. Electronic Colloquium on Computational Complexity (ECCC)(001) (2004)

Russell Impagliazzo, Philippe Moser: A zero one law for RP. IEEE Conference on Computational Complexity 2003: 48-52

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-

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Memoization and DPLL: Formula Caching Proof Systems. IEEE Conference on Computational Complexity 2003: 248-

Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel: Universal Languages and the Power of Diagonalization. IEEE Conference on Computational Complexity 2003: 337-346

Russell Impagliazzo, Bruce M. Kapron: Logics for Reasoning about Cryptographic Constructions. FOCS 2003: 372-383

Valentine Kabanets, Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. STOC 2003: 355-364

Russell Impagliazzo, Sara Miner More: Anonymous credentials with biometrically-enforced non-transferability. WPES 2003: 60-71

Russell Impagliazzo: Hardness as randomness: a survey of universal derandomization. CoRR cs.CC/0304040 (2003)

Russell Impagliazzo, Nathan Segerlind: Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. CoRR cs.CC/0308012 (2003)

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi: Homogenization and the polynomial calculus. Computational Complexity 11(3-4): 91-108 (2002)

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)

Russell Impagliazzo, Jan Krajícek: A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. 48(3): 375-377 (2002)

Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS 2002: 604-

Russell Impagliazzo, Nathan Segerlind: Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. ICALP 2002: 208-219

Valentine Kabanets, Russell Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC)(055) (2002)

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the complexity of reductions. Computational Complexity 10(2): 117-138 (2001)

Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiri Sgall: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3): 210-246 (2001)

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)

Russell Impagliazzo, Ramamohan Paturi: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2): 367-375 (2001)

Russell Impagliazzo, Ramamohan Paturi, Francis Zane: Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. 63(4): 512-530 (2001)

Russell Impagliazzo, Avi Wigderson: Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci. 63(4): 672-688 (2001)

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

Paul Beame, Russell Impagliazzo, Ashish Sabharwal: Resolution Complexity of Independent Sets in Random Graphs. IEEE Conference on Computational Complexity 2001: 52-68

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

Russell Impagliazzo, Nathan Segerlind: Counting Axioms Do Not Polynomially Simulate Counting Gates. FOCS 2001: 200-209

Russell Impagliazzo: Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. RANDOM-APPROX 2001: 2-5

Ted Carson, Russell Impagliazzo: Hill-climbing finds random planted bisections. SODA 2001: 903-909

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)

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)

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi: Homogenization and the Polynominal Calculus. ICALP 2000: 926-937

Pavel Pudlák, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. STOC 2000: 1-10

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near-Optimal Separation of Treelike and General Resolution. Electronic Colloquium on Computational Complexity (ECCC) 7(5) (2000)

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. Electronic Colloquium on Computational Complexity (ECCC) 7(9) (2000)

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)

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)

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

Russell Impagliazzo, Ramamohan Paturi: Complexity of k-SAT. IEEE Conference on Computational Complexity 1999: 237-240

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS 1999: 181-190

Eli Ben-Sasson, Russell Impagliazzo: Random CNF's are Hard for the Polynomial Calculus. FOCS 1999: 415-421

Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson: How to Forget a Secret. STACS 1999: 500-509

Giovanni Di Crescenzo, Russell Impagliazzo: Security-Preserving Hardness-Amplification for Any Regular One-Way Function. STOC 1999: 169-178

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556

Paul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Bounds for Small Distance Connectivity. Computational Complexity 7(4): 325-345 (1998)

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)

Giovanni Di Crescenzo, Russell Impagliazzo: Proofs of Membership vs. Proofs of Knowledge. IEEE Conference on Computational Complexity 1998: 34-45

Russell Impagliazzo, Ramamohan Paturi, Francis Zane: Which Problems Have Strongly Exponential Complexity? FOCS 1998: 653-663

Russell Impagliazzo, Avi Wigderson: Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS 1998: 734-743

Tassos Dimitriou, Russell Impagliazzo: Go with the Winners for Graph Bisection. SODA 1998: 510-520

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)

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)

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks: Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. 26(3): 693-707 (1997)

Arvind Gupta, Russell Impagliazzo: Bounding the Size of Planar Intertwines. SIAM J. Discrete Math. 10(3): 337-358 (1997)

Mihir Bellare, Russell Impagliazzo, Moni Naor: Does Parallel Repetition Lower the Error in Computationally Sound Protocols? FOCS 1997: 374-383

Russell Impagliazzo: Using Hard Problems to Derandomize Algorithms: An Incomplete Survey. RANDOM 1997: 165-173

Russell Impagliazzo, Avi Wigderson: P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. STOC 1997: 220-229

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the Complexity of Reductions. STOC 1997: 730-738

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)

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)

Russell Impagliazzo, Moni Naor: Efficient Cryptographic Schemes Provably as Secure as Subset Sum. J. Cryptology 9(4): 199-216 (1996)

Markus Jakobsson, Kazue Sako, Russell Impagliazzo: Designated Verifier Proofs and Their Applications. EUROCRYPT 1996: 143-154

Matthew Clegg, Jeff Edmonds, Russell Impagliazzo: Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. STOC 1996: 174-183

Tassos Dimitriou, Russell Impagliazzo: Towards an Analysis of Local Optimization Algorithms. STOC 1996: 304-313

Andrea E. F. Clementi, Russell Impagliazzo: The Reachability Problem for Finite Cellular Automata. Inf. Process. Lett. 53(1): 27-31 (1995)

Russell Impagliazzo: A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147

Russell Impagliazzo: Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995: 538-545

Paul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Vounds for Small Distance Connectivity. FOCS 1995: 692-701

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The relative complexity of NP search problems. STOC 1995: 303-314

Andrea E. F. Clementi, Russell Impagliazzo: Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata. CIAC 1994: 73-90

Russell Impagliazzo, Ran Raz, Avi Wigderson: A Direct Product Theorem. Structure in Complexity Theory Conference 1994: 88-96

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

Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart: Upper and Lower Bounds for Tree-Like Cutting Planes Proofs. LICS 1994: 220-228

Russell Impagliazzo, Noam Nisan, Avi Wigderson: Pseudorandomness for network algorithms. STOC 1994: 356-364

Toniann Pitassi, Paul Beame, Russell Impagliazzo: Exponential Lower Bounds for the Pigeonhole Principle. Computational Complexity 3: 97-140 (1993)

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)

Russell Impagliazzo, Noam Nisan: The Effect of Random Restrictions on Formula Size. Random Struct. Algorithms 4(2): 121-134 (1993)

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

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks: Size-depth trade-offs for threshold circuits. STOC 1993: 541-550

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

Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jiri Sgall: Communication Complexity Towards Lower Bounds on Circuit Depth. FOCS 1991: 249-257

Arvind Gupta, Russell Impagliazzo: Computing Planar Intertwines. FOCS 1991: 802-811

Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman: Security Preserving Amplification of Hardness. FOCS 1990: 318-326

Russell Impagliazzo, Leonid A. Levin: No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. FOCS 1990: 812-821

Russell Impagliazzo, Gábor Tardos: Decision Versus Search Problems in Super-Polynomial Time. FOCS 1989: 222-227

Russell Impagliazzo, Michael Luby: One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). FOCS 1989: 230-235

Russell Impagliazzo, Moni Naor: Efficient Cryptographic Schemes Provably as Secure as Subset Sum. FOCS 1989: 236-241

Russell Impagliazzo, David Zuckerman: How to Recycle Random Bits. FOCS 1989: 248-253

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

Russell Impagliazzo, Leonid A. Levin, Michael Luby: Pseudo-random Generation from one-way functions (Extended Abstracts). STOC 1989: 12-24

Russell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-Way Permutations. STOC 1989: 44-61

Russell Impagliazzo, Moni Naor: Decision trees and downward closures. Structure in Complexity Theory Conference 1988: 29-38

Russell Impagliazzo, Steven Rudich: Limits on the Provable Consequences of One-way Permutations. CRYPTO 1988: 8-26

Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51

Manuel Blum, Russell Impagliazzo: Generic Oracles and Oracle Classes (Extended Abstract). FOCS 1987: 118-126