default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRussell Impagliazzo
Person information
- affiliation: University of California, San Diego, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i58]Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye:
Replicability in High Dimensional Statistics. CoRR abs/2406.02628 (2024)- [i57]Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye:
The Computational Complexity of Factored Graphs. CoRR abs/2407.19102 (2024) - 2023
- [j52]Russell Impagliazzo
, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. Comput. Complex. 32(2): 6 (2023) - [c119]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM 2023: 31:1-31:21 - [c118]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC 2023: 7:1-7:24 - [c117]Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. ITCS 2023: 30:1-30:40 - [c116]Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell:
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. STOC 2023: 520-527 - [i56]Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell:
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. CoRR abs/2303.12921 (2023) - [i55]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j51]Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina:
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. Algorithmica 84(11): 3156-3191 (2022) - [c115]Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in learning. STOC 2022: 818-831 - [i54]Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in Learning. CoRR abs/2201.08430 (2022) - [i53]Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. Electron. Colloquium Comput. Complex. TR22 (2022) - [i52]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower bounds for Polynomial Calculus with extension variables over finite fields. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c114]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. CCC 2021: 6:1-6:30 - [c113]Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam:
On the Pseudo-Deterministic Query Complexity of NP Search Problems. CCC 2021: 36:1-36:22 - [c112]Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos:
Boosting in the Presence of Massart Noise. COLT 2021: 1585-1644 - [c111]Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Lifting for Constant-Depth Circuits and Applications to MCSP. ICALP 2021: 44:1-44:20 - [c110]Russell Impagliazzo, Sam McGuire:
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). ITCS 2021: 2:1-2:20 - [c109]Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina:
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. IPEC 2021: 3:1-3:15 - [i51]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. CoRR abs/2102.05019 (2021) - [i50]Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica Sorrell, Christos Tzamos:
Boosting in the Presence of Massart Noise. CoRR abs/2106.07779 (2021) - [i49]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c108]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. LICS 2020: 591-603 - [i48]Russell Impagliazzo, Sam McGuire:
Comparing computational entropies below majority (or: When is the dense model theorem false?). CoRR abs/2011.06166 (2020) - [i47]Russell Impagliazzo, Sam McGuire:
Comparing computational entropies below majority (or: When is the dense model theorem false?). Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j50]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. J. ACM 66(2): 11:1-11:16 (2019) - [j49]Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams:
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms 15(2): 23:1-23:35 (2019) - [c107]Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds Against MCSP via the Coin Problem. ICALP 2019: 66:1-66:15 - [i46]Anant Dhayal, Russell Impagliazzo:
UTIME Easy-witness Lemma & Some Consequences. Electron. Colloquium Comput. Complex. TR19 (2019) - [i45]Jiawei Gao, Russell Impagliazzo:
The Fine-Grained Complexity of Strengthenings of First-Order Logic. Electron. Colloquium Comput. Complex. TR19 (2019) - [i44]Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. TR19 (2019) - [i43]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c106]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. CCC 2018: 7:1-7:20 - [c105]Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. CCC 2018: 12:1-12:16 - [c104]Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin:
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. ICALP 2018: 27:1-27:16 - [c103]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. ITCS 2018: 10:1-10:20 - [c102]Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal:
Half-Duplex Communication Complexity. ISAAC 2018: 10:1-10:12 - [i42]Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - [i41]Marco Carmosino, Russell Impagliazzo, Manuel Sabin:
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. Electron. Colloquium Comput. Complex. TR18 (2018) - [i40]Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal:
Half-duplex communication complexity. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j48]Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. Comput. Complex. 26(1): 275-321 (2017) - [c101]Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM 2017: 35:1-35:19 - [c100]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help?. MFCS 2017: 1:1-1:13 - [c99]Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams:
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. SODA 2017: 2162-2181 - [i39]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. CoRR abs/1710.03219 (2017) - [i38]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. Electron. Colloquium Comput. Complex. TR17 (2017) - [i37]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. TR17 (2017) - [i36]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j47]Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. SIAM J. Comput. 45(4): 1612-1645 (2016) - [c98]Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness When the Odds are Against You. CCC 2016: 9:1-9:35 - [c97]Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Learning Algorithms from Natural Proofs. CCC 2016: 10:1-10:24 - [c96]Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider:
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. ITCS 2016: 261-270 - [c95]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro:
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) 2016: 235-261 - [i35]Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness when the odds are against you. Electron. Colloquium Comput. Complex. TR16 (2016) - [i34]Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Algorithms from Natural Lower Bounds. Electron. Colloquium Comput. Complex. TR16 (2016) - [i33]Jiawei Gao, Russell Impagliazzo:
Orthogonal Vectors is hard for first-order properties on sparse graphs. Electron. Colloquium Comput. Complex. TR16 (2016) - [i32]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro:
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. 2016: 760 (2016) - 2015
- [c94]Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Tighter Connections between Derandomization and Circuit Lower Bounds. APPROX-RANDOM 2015: 645-658 - [i31]Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider:
Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j46]Russell Impagliazzo, Cristopher Moore, Alexander Russell:
An Entropic Proof of Chang's Inequality. SIAM J. Discret. Math. 28(1): 173-176 (2014) - [c93]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CCC 2014: 44-55 - [c92]Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. CCC 2014: 321-332 - [i30]Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. CoRR abs/1401.5512 (2014) - [i29]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CoRR abs/1401.6848 (2014) - [i28]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. TR14 (2014) - [i27]Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j45]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
On the Exact Complexity of Evaluating Quantified k -CNF. Algorithmica 65(4): 817-827 (2013) - [c91]Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi:
Finding Heavy Hitters from Lossy or Noisy Data. APPROX-RANDOM 2013: 347-362 - [c90]Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider:
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. FOCS 2013: 479-488 - [c89]Russell Impagliazzo, Ramamohan Paturi:
Exact Complexity and Satisfiability - (Invited Talk). IPEC 2013: 1-3 - [c88]Christopher Beck, Russell Impagliazzo:
Strong ETH holds for regular resolution. STOC 2013: 487-494 - [i26]Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j44]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:1-6:48 (2012) - [j43]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. 41(6): 1722-1768 (2012) - [c87]Paul Beame, Russell Impagliazzo, Srikanth Srinivasan:
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. CCC 2012: 117-125 - [c86]Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. FOCS 2012: 101-110 - [c85]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. FOCS 2012: 111-119 - [c84]Russell Impagliazzo, William Matthews, Ramamohan Paturi:
A satisfiability algorithm for AC0. SODA 2012: 961-972 - [c83]Paul Beame, Christopher Beck, Russell Impagliazzo:
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC 2012: 213-232 - [i25]Russell Impagliazzo, Cristopher Moore, Alexander Russell:
An Entropic Proof of Chang's Inequality. CoRR abs/1205.0263 (2012) - [i24]Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider:
A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits. CoRR abs/1212.4548 (2012) - [i23]Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Electron. Colloquium Comput. Complex. TR12 (2012) - [i22]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j42]Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo:
A Stronger Model of Dynamic Programming Algorithms. Algorithmica 60(4): 938-968 (2011) - [j41]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20(4): 679-740 (2011) - [c82]Russell Impagliazzo:
Relativized Separations of Worst-Case and Average-Case Complexities for NP. CCC 2011: 104-114 - [i21]Russell Impagliazzo, William Matthews, Ramamohan Paturi:
A Satisfiability Algorithm for AC$^0$. CoRR abs/1107.3127 (2011) - [i20]Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j40]Eli Ben-Sasson, Russell Impagliazzo:
Random Cnf's are Hard for the Polynomial Calculus. Comput. Complex. 19(4): 501-519 (2010) - [j39]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637-1665 (2010) - [j38]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. ACM Trans. Comput. Theory 1(3): 9:1-9:33 (2010) - [c81]Russell Impagliazzo, Valentine Kabanets:
Constructive Proofs of Concentration Bounds. APPROX-RANDOM 2010: 617-631 - [c80]Russell Impagliazzo, Ryan Williams:
Communication Complexity with Synchronized Clocks. CCC 2010: 259-269 - [c79]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
On the Exact Complexity of Evaluating Quantified k-CNF. IPEC 2010: 50-59 - [i19]Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer:
Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex. TR10 (2010) - [i18]Russell Impagliazzo, Valentine Kabanets:
Constructive Proofs of Concentration Bounds. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j37]Sashka Davis, Russell Impagliazzo:
Models of Greedy Algorithms for Graph Problems. Algorithmica 54(3): 269-317 (2009) - [j36]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) - [j35]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Chernoff-Type Direct Product Theorems. J. Cryptol. 22(1): 75-92 (2009) - [j34]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) - [c78]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
The Complexity of Satisfiability of Small Depth Circuits. IWPEC 2009: 75-85 - [c77]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New direct-product testers and 2-query PCPs. STOC 2009: 131-140 - [c76]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
An axiomatic approach to algebrization. STOC 2009: 695-704 - [c75]Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Security Amplification for InteractiveCryptographic Primitives. TCC 2009: 128-145 - [i17]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
An Axiomatic Approach to Algebrization. Algebraic Methods in Computational Complexity 2009 - [i16]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen:
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. TR09 (2009) - [i15]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j33]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17(3): 353-376 (2008) - [j32]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) - [c74]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588 - [i14]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j31]Paul Beame, Russell Impagliazzo, Ashish Sabharwal:
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Comput. Complex. 16(3): 245-297 (2007) - [c73]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Chernoff-Type Direct Product Theorems. CRYPTO 2007: 500-516 - 2006
- [j30]Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Reducing The Seed Length In The Nisan-Wigderson Generator. Comb. 26(6): 647-681 (2006) - [j29]Russell Impagliazzo, Bruce M. Kapron:
Logics for reasoning about cryptographic constructions. J. Comput. Syst. Sci. 72(2): 286-320 (2006) - [j28]Boaz Barak, Russell Impagliazzo, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006) - [j27]Russell Impagliazzo, Nathan Segerlind:
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. 7(2): 199-218 (2006) - [c72]Sashka Davis, Jeff Edmonds, Russell Impagliazzo:
Online Algorithms to Minimize Resource Reallocations and Network Communication. APPROX-RANDOM 2006: 104-115 - [c71]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
A Duality between Clause Width and Clause Density for SAT. CCC 2006: 252-260 - [c70]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. FOCS 2006: 187-196 - [c69]Russell Impagliazzo:
Can every randomized algorithm be derandomized? STOC 2006: 373-374 - [i13]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. Electron. Colloquium Comput. Complex. TR06 (2006) - [i12]Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel:
Infinitely-Often Universal Languages and Diagonalization. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c68]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. CCC 2005: 308-322 - [c67]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. CCC 2005: 323-332 - [c66]Russell Impagliazzo:
Computational Complexity Since 1980. FSTTCS 2005: 19-47 - [i11]Sashka Davis, Russell Impagliazzo:
Models of Greedy Algorithms for Graph Problems. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j26]Valentine Kabanets, Russell Impagliazzo:
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Comput. Complex. 13(1-2): 1-46 (2004) - [j25]Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson:
Near Optimal Separation Of Tree-Like And General Resolution. Comb. 24(4): 585-603 (2004) - [j24]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) - [c65]Boaz Barak, Russell Impagliazzo, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393 - [c64]Sashka Davis, Russell Impagliazzo:
Models of greedy algorithms for graph problems. SODA 2004: 381-390 - [i10]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the complexity of succinct zero-sum games. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [c63]Russell Impagliazzo, Philippe Moser:
A zero one law for RP. CCC 2003: 48-52 - [c62]Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi:
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. CCC 2003: 135- - [c61]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems. CCC 2003: 248- - [c60]Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel:
Universal Languages and the Power of Diagonalization. CCC 2003: 337-346 - [c59]Russell Impagliazzo, Bruce M. Kapron:
Logics for Reasoning about Cryptographic Constructions. FOCS 2003: 372-383 - [c58]Valentine Kabanets, Russell Impagliazzo:
Derandomizing polynomial identity tests means proving circuit lower bounds. STOC 2003: 355-364 - [c57]Russell Impagliazzo, Sara Miner More:
Anonymous credentials with biometrically-enforced non-transferability. WPES 2003: 60-71 - [i9]Russell Impagliazzo:
Hardness as randomness: a survey of universal derandomization. CoRR cs.CC/0304040 (2003) - [i8]Russell Impagliazzo, Nathan Segerlind:
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. CoRR cs.CC/0308012 (2003) - 2002
- [j23]Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi:
Homogenization and the polynomial calculus. Comput. Complex. 11(3-4): 91-108 (2002) - [j22]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) - [j21]Russell Impagliazzo, Jan Krajícek:
A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. 48(3): 375-377 (2002) - [c56]Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS 2002: 604- - [c55]Russell Impagliazzo, Nathan Segerlind:
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. ICALP 2002: 208-219 - [i7]Valentine Kabanets, Russell Impagliazzo:
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j20]Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the complexity of reductions. Comput. Complex. 10(2): 117-138 (2001) - [j19]Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jirí Sgall:
Communication complexity towards lower bounds on circuit depth. Comput. Complex. 10(3): 210-246 (2001) - [j18]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) - [j17]Russell Impagliazzo, Ramamohan Paturi:
On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2): 367-375 (2001) - [j16]Russell Impagliazzo, Ramamohan Paturi, Francis Zane:
Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. 63(4): 512-530 (2001) - [j15]Russell Impagliazzo, Avi Wigderson:
Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci. 63(4): 672-688 (2001) - [c54]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. CCC 2001: 2-12 - [c53]Paul Beame, Russell Impagliazzo, Ashish Sabharwal:
Resolution Complexity of Independent Sets in Random Graphs. CCC 2001: 52-68 - [c52]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 - [c51]Russell Impagliazzo, Nathan Segerlind:
Counting Axioms Do Not Polynomially Simulate Counting Gates. FOCS 2001: 200-209 - [c50]Russell Impagliazzo:
Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. RANDOM-APPROX 2001: 2-5 - [c49]Ted Carson, Russell Impagliazzo:
Hill-climbing finds random planted bisections. SODA 2001: 903-909 - [i6]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (Im)possibility of Obfuscating Programs. Electron. Colloquium Comput. Complex. TR01 (2001) - [i5]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (Im)possibility of Obfuscating Programs. IACR Cryptol. ePrint Arch. 2001: 69 (2001) - 2000
- [c48]Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi:
Homogenization and the Polynominal Calculus. ICALP 2000: 926-937 - [c47]Pavel Pudlák, Russell Impagliazzo:
A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136 - [c46]Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Extractors and pseudo-random generators with optimal seed length. STOC 2000: 1-10 - [i4]Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson:
Near-Optimal Separation of Treelike and General Resolution. Electron. Colloquium Comput. Complex. TR00 (2000) - [i3]Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Extractors and pseudo-random generators with optimal seed length. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j14]Russell Impagliazzo, Pavel Pudlák, Jirí Sgall:
Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Comput. Complex. 8(2): 127-144 (1999) - [j13]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) - [c45]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). CCC 1999: 5 - [c44]Russell Impagliazzo, Ramamohan Paturi:
Complexity of k-SAT. CCC 1999: 237-240 - [c43]Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS 1999: 181-190 - [c42]Eli Ben-Sasson, Russell Impagliazzo:
Random CNF's are Hard for the Polynomial Calculus. FOCS 1999: 415-421 - [c41]Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson:
How to Forget a Secret. STACS 1999: 500-509 - [c40]Giovanni Di Crescenzo, Russell Impagliazzo:
Security-Preserving Hardness-Amplification for Any Regular One-Way Function. STOC 1999: 169-178 - [c39]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556 - [i2]Mihir Bellare, Russell Impagliazzo:
A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. IACR Cryptol. ePrint Arch. 1999: 24 (1999) - 1998
- [j12]Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Bounds for Small Distance Connectivity. Comput. Complex. 7(4): 325-345 (1998) - [j11]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) - [c38]Giovanni Di Crescenzo, Russell Impagliazzo:
Proofs of Membership vs. Proofs of Knowledge. CCC 1998: 34-45 - [c37]Russell Impagliazzo, Ramamohan Paturi, Francis Zane:
Which Problems Have Strongly Exponential Complexity? FOCS 1998: 653-663 - [c36]Russell Impagliazzo, Avi Wigderson:
Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS 1998: 734-743 - [c35]Tassos Dimitriou, Russell Impagliazzo:
Go with the Winners for Graph Bisection. SODA 1998: 510-520 - 1997
- [j10]Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall:
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. 6(3): 256-298 (1997) - [j9]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) - [j8]Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. 26(3): 693-707 (1997) - [j7]Arvind Gupta, Russell Impagliazzo:
Bounding the Size of Planar Intertwines. SIAM J. Discret. Math. 10(3): 337-358 (1997) - [c34]Mihir Bellare, Russell Impagliazzo, Moni Naor:
Does Parallel Repetition Lower the Error in Computationally Sound Protocols? FOCS 1997: 374-383 - [c33]Russell Impagliazzo:
Using Hard Problems to Derandomize Algorithms: An Incomplete Survey. RANDOM 1997: 165-173 - [c32]Russell Impagliazzo, Avi Wigderson:
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. STOC 1997: 220-229 - [c31]Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the Complexity of Reductions. STOC 1997: 730-738 - [i1]Russell Impagliazzo, Pavel Pudlák, Jirí Sgall:
Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j6]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) - [j5]Russell Impagliazzo, Moni Naor:
Efficient Cryptographic Schemes Provably as Secure as Subset Sum. J. Cryptol. 9(4): 199-216 (1996) - [c30]Markus Jakobsson, Kazue Sako, Russell Impagliazzo:
Designated Verifier Proofs and Their Applications. EUROCRYPT 1996: 143-154 - [c29]Matthew Clegg, Jeff Edmonds, Russell Impagliazzo:
Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. STOC 1996: 174-183 - [c28]Tassos Dimitriou, Russell Impagliazzo:
Towards an Analysis of Local Optimization Algorithms. STOC 1996: 304-313 - 1995
- [j4]Andrea Clementi, Russell Impagliazzo:
The Reachability Problem for Finite Cellular Automata. Inf. Process. Lett. 53(1): 27-31 (1995) - [c27]Russell Impagliazzo:
A Personal View of Average-Case Complexity. SCT 1995: 134-147 - [c26]Russell Impagliazzo:
Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995: 538-545 - [c25]Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Vounds for Small Distance Connectivity. FOCS 1995: 692-701 - [c24]Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi:
The relative complexity of NP search problems. STOC 1995: 303-314 - 1994
- [c23]Andrea Clementi, Russell Impagliazzo:
Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata. CIAC 1994: 73-90 - [c22]Russell Impagliazzo, Ran Raz, Avi Wigderson:
A Direct Product Theorem. SCT 1994: 88-96 - [c21]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 - [c20]Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart:
Upper and Lower Bounds for Tree-Like Cutting Planes Proofs. LICS 1994: 220-228 - [c19]Russell Impagliazzo, Noam Nisan, Avi Wigderson:
Pseudorandomness for network algorithms. STOC 1994: 356-364 - 1993
- [j3]Toniann Pitassi, Paul Beame, Russell Impagliazzo:
Exponential Lower Bounds for the Pigeonhole Principle. Comput. Complex. 3: 97-140 (1993) - [j2]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) - [j1]Russell Impagliazzo, Noam Nisan:
The Effect of Random Restrictions on Formula Size. Random Struct. Algorithms 4(2): 121-134 (1993) - [c18]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 - [c17]Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
Size-depth trade-offs for threshold circuits. STOC 1993: 541-550 - 1992
- [c16]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
- [c15]Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jirí Sgall:
Communication Complexity Towards Lower Bounds on Circuit Depth. FOCS 1991: 249-257 - [c14]Arvind Gupta, Russell Impagliazzo:
Computing Planar Intertwines. FOCS 1991: 802-811 - 1990
- [c13]Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman:
Security Preserving Amplification of Hardness. FOCS 1990: 318-326 - [c12]Russell Impagliazzo, Leonid A. Levin:
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. FOCS 1990: 812-821
1980 – 1989
- 1989
- [c11]Russell Impagliazzo, Gábor Tardos:
Decision Versus Search Problems in Super-Polynomial Time. FOCS 1989: 222-227 - [c10]Russell Impagliazzo, Michael Luby:
One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). FOCS 1989: 230-235 - [c9]Russell Impagliazzo, Moni Naor:
Efficient Cryptographic Schemes Provably as Secure as Subset Sum. FOCS 1989: 236-241 - [c8]Russell Impagliazzo, David Zuckerman:
How to Recycle Random Bits. FOCS 1989: 248-253 - [c7]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 - [c6]Russell Impagliazzo, Leonid A. Levin, Michael Luby:
Pseudo-random Generation from one-way functions (Extended Abstracts). STOC 1989: 12-24 - [c5]Russell Impagliazzo, Steven Rudich:
Limits on the Provable Consequences of One-Way Permutations. STOC 1989: 44-61 - 1988
- [c4]Russell Impagliazzo, Moni Naor:
Decision trees and downward closures. SCT 1988: 29-38 - [c3]Russell Impagliazzo, Steven Rudich:
Limits on the Provable Consequences of One-way Permutations. CRYPTO 1988: 8-26 - 1987
- [c2]Russell Impagliazzo, Moti Yung:
Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 - [c1]Manuel Blum, Russell Impagliazzo:
Generic Oracles and Oracle Classes (Extended Abstract). FOCS 1987: 118-126
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:18 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
