2009 |
120 | EE | Yevgeniy Dodis,
Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets:
Security Amplification for InteractiveCryptographic Primitives.
TCC 2009: 128-145 |
119 | EE | Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets:
Chernoff-Type Direct Product Theorems.
J. Cryptology 22(1): 75-92 (2009) |
2008 |
118 | EE | Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets,
Avi Wigderson:
Uniform direct product theorems: simplified, optimized, and derandomized.
STOC 2008: 579-588 |
117 | EE | Lance Fortnow,
Russell Impagliazzo,
Valentine Kabanets,
Christopher Umans:
On the Complexity of Succinct Zero-Sum Games.
Computational Complexity 17(3): 353-376 (2008) |
116 | EE | 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) |
115 | EE | 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 |
114 | EE | Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets:
Chernoff-Type Direct Product Theorems.
CRYPTO 2007: 500-516 |
113 | EE | 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 |
112 | EE | Sashka Davis,
Jeff Edmonds,
Russell Impagliazzo:
Online Algorithms to Minimize Resource Reallocations and Network Communication.
APPROX-RANDOM 2006: 104-115 |
111 | EE | Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets:
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.
FOCS 2006: 187-196 |
110 | EE | Chris Calabro,
Russell Impagliazzo,
Ramamohan Paturi:
A Duality between Clause Width and Clause Density for SAT.
IEEE Conference on Computational Complexity 2006: 252-260 |
109 | EE | Russell Impagliazzo:
Can every randomized algorithm be derandomized?
STOC 2006: 373-374 |
108 | EE | Russell Impagliazzo,
Nathan Segerlind:
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.
ACM Trans. Comput. Log. 7(2): 199-218 (2006) |
107 | EE | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Reducing The Seed Length In The Nisan-Wigderson Generator.
Combinatorica 26(6): 647-681 (2006) |
106 | EE | Alan Nash,
Russell Impagliazzo,
Jeffrey B. Remmel:
Infinitely-Often Universal Languages and Diagonalization.
Electronic Colloquium on Computational Complexity (ECCC) 13(051): (2006) |
105 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Formula Caching in DPLL.
Electronic Colloquium on Computational Complexity (ECCC) 13(140): (2006) |
104 | EE | Russell Impagliazzo,
Bruce M. Kapron:
Logics for reasoning about cryptographic constructions.
J. Comput. Syst. Sci. 72(2): 286-320 (2006) |
103 | EE | Boaz Barak,
Russell Impagliazzo,
Avi Wigderson:
Extracting Randomness Using Few Independent Sources.
SIAM J. Comput. 36(4): 1095-1118 (2006) |
2005 |
102 | EE | Russell Impagliazzo:
Computational Complexity Since 1980.
FSTTCS 2005: 19-47 |
101 | EE | 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 |
100 | EE | Lance Fortnow,
Russell Impagliazzo,
Valentine Kabanets,
Christopher Umans:
On the Complexity of Succinct Zero-Sum Games.
IEEE Conference on Computational Complexity 2005: 323-332 |
99 | EE | Sashka Davis,
Russell Impagliazzo:
Models of Greedy Algorithms for Graph Problems
Electronic Colloquium on Computational Complexity (ECCC)(120): (2005) |
2004 |
98 | EE | Boaz Barak,
Russell Impagliazzo,
Avi Wigderson:
Extracting Randomness Using Few Independent Sources.
FOCS 2004: 384-393 |
97 | EE | Sashka Davis,
Russell Impagliazzo:
Models of greedy algorithms for graph problems.
SODA 2004: 381-390 |
96 | EE | Eli Ben-Sasson,
Russell Impagliazzo,
Avi Wigderson:
Near Optimal Separation Of Tree-Like And General Resolution.
Combinatorica 24(4): 585-603 (2004) |
95 | EE | Valentine Kabanets,
Russell Impagliazzo:
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.
Computational Complexity 13(1-2): 1-46 (2004) |
94 | EE | Lance Fortnow,
Russell Impagliazzo,
Valentine Kabanets,
Christopher Umans:
On the complexity of succinct zero-sum games
Electronic Colloquium on Computational Complexity (ECCC)(001): (2004) |
93 | EE | 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 |
92 | EE | Russell Impagliazzo,
Bruce M. Kapron:
Logics for Reasoning about Cryptographic Constructions.
FOCS 2003: 372-383 |
91 | EE | 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- |
90 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems.
IEEE Conference on Computational Complexity 2003: 248- |
89 | EE | Alan Nash,
Russell Impagliazzo,
Jeffrey B. Remmel:
Universal Languages and the Power of Diagonalization.
IEEE Conference on Computational Complexity 2003: 337-346 |
88 | EE | Russell Impagliazzo,
Philippe Moser:
A zero one law for RP.
IEEE Conference on Computational Complexity 2003: 48-52 |
87 | EE | Valentine Kabanets,
Russell Impagliazzo:
Derandomizing polynomial identity tests means proving circuit lower bounds.
STOC 2003: 355-364 |
86 | EE | Russell Impagliazzo,
Sara Miner More:
Anonymous credentials with biometrically-enforced non-transferability.
WPES 2003: 60-71 |
85 | EE | Russell Impagliazzo:
Hardness as randomness: a survey of universal derandomization
CoRR cs.CC/0304040: (2003) |
84 | EE | Russell Impagliazzo,
Nathan Segerlind:
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
CoRR cs.CC/0308012: (2003) |
2002 |
83 | EE | Nathan Segerlind,
Samuel R. Buss,
Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.
FOCS 2002: 604- |
82 | EE | Russell Impagliazzo,
Nathan Segerlind:
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.
ICALP 2002: 208-219 |
81 | EE | Josh Buresh-Oppenheim,
Matthew Clegg,
Russell Impagliazzo,
Toniann Pitassi:
Homogenization and the polynomial calculus.
Computational Complexity 11(3-4): 91-108 (2002) |
80 | EE | Valentine Kabanets,
Russell Impagliazzo:
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
Electronic Colloquium on Computational Complexity (ECCC)(055): (2002) |
79 | EE | 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) |
78 | EE | Russell Impagliazzo,
Jan Krajícek:
A Note on Conservativity Relations among Bounded Arithmetic Theories.
Math. Log. Q. 48(3): 375-377 (2002) |
2001 |
77 | 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 |
76 | | Russell Impagliazzo,
Nathan Segerlind:
Counting Axioms Do Not Polynomially Simulate Counting Gates.
FOCS 2001: 200-209 |
75 | EE | 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 |
74 | EE | Paul Beame,
Russell Impagliazzo,
Ashish Sabharwal:
Resolution Complexity of Independent Sets in Random Graphs.
IEEE Conference on Computational Complexity 2001: 52-68 |
73 | EE | Russell Impagliazzo:
Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems.
RANDOM-APPROX 2001: 2-5 |
72 | EE | Ted Carson,
Russell Impagliazzo:
Hill-climbing finds random planted bisections.
SODA 2001: 903-909 |
71 | EE | Manindra Agrawal,
Eric Allender,
Russell Impagliazzo,
Toniann Pitassi,
Steven Rudich:
Reducing the complexity of reductions.
Computational Complexity 10(2): 117-138 (2001) |
70 | EE | Jeff Edmonds,
Russell Impagliazzo,
Steven Rudich,
Jiri Sgall:
Communication complexity towards lower bounds on circuit depth.
Computational Complexity 10(3): 210-246 (2001) |
69 | 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) |
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 | EE | Russell Impagliazzo,
Ramamohan Paturi,
Francis Zane:
Which Problems Have Strongly Exponential Complexity?
J. Comput. Syst. Sci. 63(4): 512-530 (2001) |
65 | EE | Russell Impagliazzo,
Avi Wigderson:
Randomness vs Time: Derandomization under a Uniform Assumption.
J. Comput. Syst. Sci. 63(4): 672-688 (2001) |
2000 |
64 | EE | Josh Buresh-Oppenheim,
Matthew Clegg,
Russell Impagliazzo,
Toniann Pitassi:
Homogenization and the Polynominal Calculus.
ICALP 2000: 926-937 |
63 | EE | Pavel Pudlák,
Russell Impagliazzo:
A lower bound for DLL algorithms for k-SAT (preliminary version).
SODA 2000: 128-136 |
62 | EE | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Extractors and pseudo-random generators with optimal seed length.
STOC 2000: 1-10 |
61 | EE | 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 | EE | 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 | EE | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Near-Optimal Conversion of Hardness into Pseudo-Randomness.
FOCS 1999: 181-190 |
58 | EE | Eli Ben-Sasson,
Russell Impagliazzo:
Random CNF's are Hard for the Polynomial Calculus.
FOCS 1999: 415-421 |
57 | EE | Russell Impagliazzo,
Ramamohan Paturi:
Complexity of k-SAT.
IEEE Conference on Computational Complexity 1999: 237-240 |
56 | EE | 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 | EE | Giovanni Di Crescenzo,
Niels Ferguson,
Russell Impagliazzo,
Markus Jakobsson:
How to Forget a Secret.
STACS 1999: 500-509 |
54 | EE | Giovanni Di Crescenzo,
Russell Impagliazzo:
Security-Preserving Hardness-Amplification for Any Regular One-Way Function.
STOC 1999: 169-178 |
53 | EE | 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 | EE | Russell Impagliazzo,
Ramamohan Paturi,
Francis Zane:
Which Problems Have Strongly Exponential Complexity?
FOCS 1998: 653-663 |
49 | EE | Russell Impagliazzo,
Avi Wigderson:
Randomness vs. Time: De-Randomization under a Uniform Assumption.
FOCS 1998: 734-743 |
48 | EE | 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 | EE | 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 | EE | 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 | EE | Russell Impagliazzo,
Avi Wigderson:
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.
STOC 1997: 220-229 |
41 | EE | 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 | EE | 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 | EE | Arvind Gupta,
Russell Impagliazzo:
Bounding the Size of Planar Intertwines.
SIAM J. Discrete Math. 10(3): 337-358 (1997) |
1996 |
35 | EE | Markus Jakobsson,
Kazue Sako,
Russell Impagliazzo:
Designated Verifier Proofs and Their Applications.
EUROCRYPT 1996: 143-154 |
34 | EE | Matthew Clegg,
Jeff Edmonds,
Russell Impagliazzo:
Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability.
STOC 1996: 174-183 |
33 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Russell Impagliazzo,
Steven Rudich:
Limits on the Provable Consequences of One-way Permutations.
CRYPTO 1988: 8-26 |
1987 |
2 | EE | 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 |