Russell Impagliazzo

239 papers A* 68A 33B 6C 1Journal 116Unranked 15

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	High Rate Efficient Local List Decoding from HDX. CoRR Yotam Dikstein, Max Hopkins, Russell Impagliazzo, Toniann Pitassi
2025	J	`jnl`	Approximate Replicability in Learning. CoRR Max Hopkins, Russell Impagliazzo, Christopher Ye
2025	A	`conf`	Lifting to Randomized Parity Decision Trees. APPROX/RANDOM Farzan Byramji, Russell Impagliazzo
2025	J	`jnl`	Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities. CoRR Farzan Byramji, Russell Impagliazzo
2025	J	`jnl`	Lower bounds for the Bit Pigeonhole Principle in Bounded-Depth Resolution over Parities. Electron. Colloquium Comput. Complex. Farzan Byramji, Russell Impagliazzo
2025	A*	`conf`	Stronger Cell Probe Lower Bounds via Local PRGs. FOCS Oliver Korten, Toniann Pitassi, Russell Impagliazzo
2025	J	`jnl`	Stronger Cell Probe Lower Bounds via Local PRGs. Electron. Colloquium Comput. Complex. Oliver Korten, Toniann Pitassi, Russell Impagliazzo
2025	A	`conf`	The Computational Complexity of Factored Graphs. ITCS Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye
2024	J	`jnl`	Lifting to Randomized Parity Decision Trees. Electron. Colloquium Comput. Complex. Farzan Byramji, Russell Impagliazzo
2024	A*	`conf`	Replicability in High Dimensional Statistics. FOCS Max Hopkins, Russell Impagliazzo, Daniel M. Kane, Sihan Liu, Christopher Ye
2024	J	`jnl`	Replicability in High Dimensional Statistics. CoRR Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye
2024	J	`jnl`	The Computational Complexity of Factored Graphs. CoRR Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye
2024	J	`jnl`	The Greedy Coin Change Problem. CoRR Shreya Gupta, Boyang Huang, Russell Impagliazzo
2023	A	`conf`	Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
2023	J	`jnl`	Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	A*	`conf`	Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. STOC Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell
2023	J	`jnl`	Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. CoRR Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell
2023	A	`conf`	Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	A	`conf`	TFNP Characterizations of Proof Systems and Monotone Circuits. ITCS Sam Buss, Noah Fleming, Russell Impagliazzo
2023	J	`jnl`	The Power of Natural Properties as Oracles. Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2022	J	`jnl`	Lower bounds for Polynomial Calculus with extension variables over finite fields. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
2022	J	`jnl`	Reproducibility in Learning. CoRR Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell
2022	A*	`conf`	Reproducibility in learning. STOC Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell
2022	J	`jnl`	TFNP Characterizations of Proof Systems and Monotone Circuits. Electron. Colloquium Comput. Complex. Sam Buss, Noah Fleming, Russell Impagliazzo
2022	J	`jnl`	The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. Algorithmica Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina
2021	A*	`conf`	Boosting in the Presence of Massart Noise. COLT Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
2021	J	`jnl`	Boosting in the Presence of Massart Noise. CoRR Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
2021	A	`conf`	Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). ITCS Russell Impagliazzo, Sam McGuire
2021	A*	`conf`	Lifting for Constant-Depth Circuits and Applications to MCSP. ICALP Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2021	A	`conf`	On the Power and Limitations of Branch and Cut. CCC Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021	J	`jnl`	On the Power and Limitations of Branch and Cut. CoRR Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021	J	`jnl`	On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021	A	`conf`	On the Pseudo-Deterministic Query Complexity of NP Search Problems. CCC Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam
2021	B	`conf`	The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. IPEC Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina
2020	J	`jnl`	Comparing computational entropies below majority (or: When is the dense model theorem false?). CoRR Russell Impagliazzo, Sam McGuire
2020	J	`jnl`	Comparing computational entropies below majority (or: When is the dense model theorem false?). Electron. Colloquium Comput. Complex. Russell Impagliazzo, Sam McGuire
2020	A*	`conf`	The Surprising Power of Constant Depth Algebraic Proofs. LICS Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
2019	A*	`conf`	AC ICALP Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019	J	`jnl`	AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
2019	J	`jnl`	Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams
2019	J	`jnl`	Pseudorandomness from Shrinkage. J. ACM Russell Impagliazzo, Raghu Meka, David Zuckerman
2019	J	`jnl`	The Fine-Grained Complexity of Strengthenings of First-Order Logic. Electron. Colloquium Comput. Complex. Jiawei Gao, Russell Impagliazzo
2019	J	`jnl`	The Surprising Power of Constant Depth Algebraic Proofs. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
2019	J	`jnl`	UTIME Easy-witness Lemma & Some Consequences. Electron. Colloquium Comput. Complex. Anant Dhayal, Russell Impagliazzo
2018	A*	`conf`	Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. ICALP Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin
2018	J	`jnl`	Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. Electron. Colloquium Comput. Complex. Marco Carmosino, Russell Impagliazzo, Manuel Sabin
2018	B	`conf`	Half-Duplex Communication Complexity. ISAAC Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal
2018	J	`jnl`	Half-duplex communication complexity. Electron. Colloquium Comput. Complex. Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
2018	A	`conf`	Hardness Amplification for Non-Commutative Arithmetic Circuits. CCC Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
2018	J	`jnl`	Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
2018	A	`conf`	Stabbing Planes. ITCS Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2018	A	`conf`	The Power of Natural Properties as Oracles. CCC Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2017	—	`conf`	Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2017	A*	`conf`	Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. SODA Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams
2017	J	`jnl`	Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
2017	B	`conf`	Does Looking Inside a Circuit Help?. MFCS Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
2017	J	`jnl`	Fourier Concentration from Shrinkage. Comput. Complex. Russell Impagliazzo, Valentine Kabanets
2017	J	`jnl`	Stabbing Planes. CoRR Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2017	J	`jnl`	Stabbing Planes. Electron. Colloquium Comput. Complex. Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2017	J	`jnl`	The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2016	J	`jnl`	Algorithms from Natural Lower Bounds. Electron. Colloquium Comput. Complex. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2016	A	`conf`	Learning Algorithms from Natural Proofs. CCC Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2016	A	`conf`	Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. ITCS Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider
2016	J	`jnl`	Orthogonal Vectors is hard for first-order properties on sparse graphs. Electron. Colloquium Comput. Complex. Jiawei Gao, Russell Impagliazzo
2016	A	`conf`	Pseudorandomness When the Odds are Against You. CCC Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
2016	J	`jnl`	Pseudorandomness when the odds are against you. Electron. Colloquium Comput. Complex. Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
2016	—	`conf`	Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
2016	J	`jnl`	Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro
2016	J	`jnl`	Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. SIAM J. Comput. Paul Beame, Chris Beck, Russell Impagliazzo
2015	J	`jnl`	Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. Electron. Colloquium Comput. Complex. Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider
2015	—	`conf`	Tighter Connections between Derandomization and Circuit Lower Bounds. APPROX-RANDOM Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2014	J	`jnl`	0-1 Integer Linear Programming with a Linear Number of Constraints. CoRR Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
2014	J	`jnl`	0-1 Integer Linear Programming with a Linear Number of Constraints. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
2014	A	`conf`	AM with Multiple Merlins. CCC Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
2014	J	`jnl`	AM with Multiple Merlins. CoRR Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
2014	J	`jnl`	AM with Multiple Merlins. Electron. Colloquium Comput. Complex. Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
2014	J	`jnl`	An Entropic Proof of Chang's Inequality. SIAM J. Discret. Math. Russell Impagliazzo, Cristopher Moore, Alexander Russell
2014	A	`conf`	Fourier Concentration from Shrinkage. CCC Russell Impagliazzo, Valentine Kabanets
2013	A*	`conf`	A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. FOCS Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
2013	B	`conf`	Exact Complexity and Satisfiability - (Invited Talk). IPEC Russell Impagliazzo, Ramamohan Paturi
2013	—	`conf`	Finding Heavy Hitters from Lossy or Noisy Data. APPROX-RANDOM Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi
2013	J	`jnl`	Fourier Concentration from Shrinkage. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets
2013	J	`jnl`	On the Exact Complexity of Evaluating Quantified Algorithmica Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2013	A*	`conf`	Strong ETH holds for regular resolution. STOC Christopher Beck, Russell Impagliazzo
2012	J	`jnl`	A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits CoRR Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
2012	A*	`conf`	A satisfiability algorithm for AC SODA Russell Impagliazzo, William Matthews, Ramamohan Paturi
2012	J	`jnl`	An Entropic Proof of Chang's Inequality CoRR Russell Impagliazzo, Cristopher Moore, Alexander Russell
2012	A	`conf`	Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. CCC Paul Beame, Russell Impagliazzo, Srikanth Srinivasan
2012	A*	`conf`	Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. FOCS Chris Beck, Russell Impagliazzo, Shachar Lovett
2012	J	`jnl`	Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Electron. Colloquium Comput. Complex. Chris Beck, Russell Impagliazzo, Shachar Lovett
2012	J	`jnl`	New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2012	J	`jnl`	On the (im)possibility of obfuscating programs. J. ACM Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2012	A*	`conf`	Pseudorandomness from Shrinkage. FOCS Russell Impagliazzo, Raghu Meka, David Zuckerman
2012	J	`jnl`	Pseudorandomness from Shrinkage. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Raghu Meka, David Zuckerman
2012	A*	`conf`	Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC Paul Beame, Christopher Beck, Russell Impagliazzo
2011	J	`jnl`	A Satisfiability Algorithm for AC$^0$ CoRR Russell Impagliazzo, William Matthews, Ramamohan Paturi
2011	J	`jnl`	A Stronger Model of Dynamic Programming Algorithms. Algorithmica Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo
2011	A	`conf`	Relativized Separations of Worst-Case and Average-Case Complexities for NP. CCC Russell Impagliazzo
2011	J	`jnl`	Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electron. Colloquium Comput. Complex. Paul Beame, Chris Beck, Russell Impagliazzo
2011	J	`jnl`	Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2010	A	`conf`	Communication Complexity with Synchronized Clocks. CCC Russell Impagliazzo, Ryan Williams
2010	—	`conf`	Constructive Proofs of Concentration Bounds. APPROX-RANDOM Russell Impagliazzo, Valentine Kabanets
2010	J	`jnl`	Constructive Proofs of Concentration Bounds. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets
2010	J	`jnl`	Formula Caching in DPLL. ACM Trans. Comput. Theory Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2010	J	`jnl`	Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex. Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer
2010	B	`conf`	On the Exact Complexity of Evaluating Quantified IPEC Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2010	J	`jnl`	Random Cnf's are Hard for the Polynomial Calculus. Comput. Complex. Eli Ben-Sasson, Russell Impagliazzo
2010	J	`jnl`	Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2009	J	`jnl`	A zero-one law for RP and derandomization of AM if NP is not small. Inf. Comput. Russell Impagliazzo, Philippe Moser
2009	—	`conf`	An Axiomatic Approach to Algebrization. Algebraic Methods in Computational Complexity Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2009	A*	`conf`	An axiomatic approach to algebrization. STOC Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
2009	J	`jnl`	Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2009	J	`jnl`	Chernoff-Type Direct Product Theorems. J. Cryptol. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2009	J	`jnl`	Models of Greedy Algorithms for Graph Problems. Algorithmica Sashka Davis, Russell Impagliazzo
2009	J	`jnl`	New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2009	A*	`conf`	New direct-product testers and 2-query PCPs. STOC Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2009	B	`conf`	Security Amplification for InteractiveCryptographic Primitives. TCC Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2009	—	`conf`	The Complexity of Satisfiability of Small Depth Circuits. IWPEC Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2009	J	`jnl`	Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
2008	J	`jnl`	On the Complexity of Succinct Zero-Sum Games. Comput. Complex. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2008	J	`jnl`	The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. J. Comput. Syst. Sci. Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
2008	J	`jnl`	Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2008	A*	`conf`	Uniform direct product theorems: simplified, optimized, and derandomized. STOC Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
2007	A*	`conf`	Chernoff-Type Direct Product Theorems. CRYPTO Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2007	J	`jnl`	The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Comput. Complex. Paul Beame, Russell Impagliazzo, Ashish Sabharwal
2006	A	`conf`	A Duality between Clause Width and Clause Density for SAT. CCC Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2006	A*	`conf`	Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. FOCS Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
2006	A*	`conf`	Can every randomized algorithm be derandomized? STOC Russell Impagliazzo
2006	J	`jnl`	Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. Russell Impagliazzo, Nathan Segerlind
2006	J	`jnl`	Extracting Randomness Using Few Independent Sources. SIAM J. Comput. Boaz Barak, Russell Impagliazzo, Avi Wigderson
2006	J	`jnl`	Formula Caching in DPLL. Electron. Colloquium Comput. Complex. Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2006	J	`jnl`	Infinitely-Often Universal Languages and Diagonalization. Electron. Colloquium Comput. Complex. Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel
2006	J	`jnl`	Logics for reasoning about cryptographic constructions. J. Comput. Syst. Sci. Russell Impagliazzo, Bruce M. Kapron
2006	—	`conf`	Online Algorithms to Minimize Resource Reallocations and Network Communication. APPROX-RANDOM Sashka Davis, Jeff Edmonds, Russell Impagliazzo
2006	J	`jnl`	Reducing The Seed Length In The Nisan-Wigderson Generator. Comb. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
2005	—	`conf`	Computational Complexity Since 1980. FSTTCS Russell Impagliazzo
2005	J	`jnl`	Models of Greedy Algorithms for Graph Problems Electron. Colloquium Comput. Complex. Sashka Davis, Russell Impagliazzo
2005	A	`conf`	On the Complexity of Succinct Zero-Sum Games. CCC Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2005	A	`conf`	Toward a Model for Backtracking and Dynamic Programming. CCC Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2004	J	`jnl`	A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution. SIAM J. Comput. Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo
2004	J	`jnl`	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Comput. Complex. Valentine Kabanets, Russell Impagliazzo
2004	A*	`conf`	Extracting Randomness Using Few Independent Sources. FOCS Boaz Barak, Russell Impagliazzo, Avi Wigderson
2004	A*	`conf`	Models of greedy algorithms for graph problems. SODA Sashka Davis, Russell Impagliazzo
2004	J	`jnl`	Near Optimal Separation Of Tree-Like And General Resolution. Comb. Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson
2004	J	`jnl`	On the complexity of succinct zero-sum games Electron. Colloquium Comput. Complex. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
2003	A	`conf`	A zero one law for RP. CCC Russell Impagliazzo, Philippe Moser
2003	—	`conf`	Anonymous credentials with biometrically-enforced non-transferability. WPES Russell Impagliazzo, Sara Miner More
2003	J	`jnl`	Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations CoRR Russell Impagliazzo, Nathan Segerlind
2003	A*	`conf`	Derandomizing polynomial identity tests means proving circuit lower bounds. STOC Valentine Kabanets, Russell Impagliazzo
2003	J	`jnl`	Hardness as randomness: a survey of universal derandomization CoRR Russell Impagliazzo
2003	A*	`conf`	Logics for Reasoning about Cryptographic Constructions. FOCS Russell Impagliazzo, Bruce M. Kapron
2003	A	`conf`	Memoization and DPLL: Formula Caching Proof Systems. CCC Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
2003	A	`conf`	The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. CCC Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
2003	A	`conf`	Universal Languages and the Power of Diagonalization. CCC Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel
2002	J	`jnl`	A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. Russell Impagliazzo, Jan Krajícek
2002	A*	`conf`	A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo
2002	A*	`conf`	Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. ICALP Russell Impagliazzo, Nathan Segerlind
2002	J	`jnl`	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds Electron. Colloquium Comput. Complex. Valentine Kabanets, Russell Impagliazzo
2002	J	`jnl`	Homogenization and the polynomial calculus. Comput. Complex. Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi
2002	J	`jnl`	In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2001	J	`jnl`	Communication complexity towards lower bounds on circuit depth. Comput. Complex. Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jirí Sgall
2001	A*	`conf`	Counting Axioms Do Not Polynomially Simulate Counting Gates. FOCS Russell Impagliazzo, Nathan Segerlind
2001	—	`conf`	Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. RANDOM-APPROX Russell Impagliazzo
2001	A*	`conf`	Hill-climbing finds random planted bisections. SODA Ted Carson, Russell Impagliazzo
2001	A	`conf`	In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. CCC Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
2001	J	`jnl`	Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
2001	J	`jnl`	On the (Im)possibility of Obfuscating Programs Electron. Colloquium Comput. Complex. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2001	A*	`conf`	On the (Im)possibility of Obfuscating Programs. CRYPTO Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2001	J	`jnl`	On the (Im)possibility of Obfuscating Programs. IACR Cryptol. ePrint Arch. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2001	J	`jnl`	On the Complexity of k-SAT. J. Comput. Syst. Sci. Russell Impagliazzo, Ramamohan Paturi
2001	J	`jnl`	Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci. Russell Impagliazzo, Avi Wigderson
2001	J	`jnl`	Reducing the complexity of reductions. Comput. Complex. Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
2001	A	`conf`	Resolution Complexity of Independent Sets in Random Graphs. CCC Paul Beame, Russell Impagliazzo, Ashish Sabharwal
2001	J	`jnl`	Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. Russell Impagliazzo, Ramamohan Paturi, Francis Zane
2000	A*	`conf`	A lower bound for DLL algorithms for SODA Pavel Pudlák, Russell Impagliazzo
2000	J	`jnl`	Extractors and pseudo-random generators with optimal seed length Electron. Colloquium Comput. Complex. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
2000	A*	`conf`	Extractors and pseudo-random generators with optimal seed length. STOC Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
2000	A*	`conf`	Homogenization and the Polynominal Calculus. ICALP Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi
2000	J	`jnl`	Near-Optimal Separation of Treelike and General Resolution Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson
1999	J	`jnl`	A Pseudorandom Generator from any One-way Function. SIAM J. Comput. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
1999	J	`jnl`	A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. IACR Cryptol. ePrint Arch. Mihir Bellare, Russell Impagliazzo
1999	A	`conf`	Complexity of k-SAT. CCC Russell Impagliazzo, Ramamohan Paturi
1999	A	`conf`	How to Forget a Secret. STACS Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson
1999	A	`conf`	Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). CCC Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
1999	A*	`conf`	Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
1999	J	`jnl`	Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Comput. Complex. Russell Impagliazzo, Pavel Pudlák, Jirí Sgall
1999	A*	`conf`	Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
1999	A*	`conf`	Random CNF's are Hard for the Polynomial Calculus. FOCS Eli Ben-Sasson, Russell Impagliazzo
1999	A*	`conf`	Security-Preserving Hardness-Amplification for Any Regular One-Way Function. STOC Giovanni Di Crescenzo, Russell Impagliazzo
1998	A*	`conf`	Go with the Winners for Graph Bisection. SODA Tassos Dimitriou, Russell Impagliazzo
1998	J	`jnl`	Improved Depth Lower Bounds for Small Distance Connectivity. Comput. Complex. Paul Beame, Russell Impagliazzo, Toniann Pitassi
1998	A	`conf`	Proofs of Membership vs. Proofs of Knowledge. CCC Giovanni Di Crescenzo, Russell Impagliazzo
1998	A*	`conf`	Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS Russell Impagliazzo, Avi Wigderson
1998	J	`jnl`	The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
1998	A*	`conf`	Which Problems Have Strongly Exponential Complexity? FOCS Russell Impagliazzo, Ramamohan Paturi, Francis Zane
1997	J	`jnl`	A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory. Inf. Comput. Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami
1997	J	`jnl`	Bounding the Size of Planar Intertwines. SIAM J. Discret. Math. Arvind Gupta, Russell Impagliazzo
1997	A*	`conf`	Does Parallel Repetition Lower the Error in Computationally Sound Protocols? FOCS Mihir Bellare, Russell Impagliazzo, Moni Naor
1997	J	`jnl`	Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm Electron. Colloquium Comput. Complex. Russell Impagliazzo, Pavel Pudlák, Jirí Sgall
1997	J	`jnl`	Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall
1997	A*	`conf`	Reducing the Complexity of Reductions. STOC Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
1997	J	`jnl`	Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks
1997	—	`conf`	Using Hard Problems to Derandomize Algorithms: An Incomplete Survey. RANDOM Russell Impagliazzo
1996	A*	`conf`	Designated Verifier Proofs and Their Applications. EUROCRYPT Markus Jakobsson, Kazue Sako, Russell Impagliazzo
1996	J	`jnl`	Efficient Cryptographic Schemes Provably as Secure as Subset Sum. J. Cryptol. Russell Impagliazzo, Moni Naor
1996	J	`jnl`	Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. J. Comput. Syst. Sci. Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski
1996	A*	`conf`	Towards an Analysis of Local Optimization Algorithms. STOC Tassos Dimitriou, Russell Impagliazzo
1996	A*	`conf`	Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. STOC Matthew Clegg, Jeff Edmonds, Russell Impagliazzo
1995	—	`conf`	A Personal View of Average-Case Complexity. SCT Russell Impagliazzo
1995	A*	`conf`	Hard-Core Distributions for Somewhat Hard Problems. FOCS Russell Impagliazzo
1995	A*	`conf`	Improved Depth Lower Vounds for Small Distance Connectivity. FOCS Paul Beame, Russell Impagliazzo, Toniann Pitassi
1995	J	`jnl`	The Reachability Problem for Finite Cellular Automata. Inf. Process. Lett. Andrea Clementi, Russell Impagliazzo
1995	A*	`conf`	The relative complexity of NP search problems. STOC Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
1994	—	`conf`	A Direct Product Theorem. SCT Russell Impagliazzo, Ran Raz, Avi Wigderson
1994	C	`conf`	Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata. CIAC Andrea Clementi, Russell Impagliazzo
1994	A*	`conf`	Lower Bound on Hilbert's Nullstellensatz and propositional proofs FOCS Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák
1994	A*	`conf`	Pseudorandomness for network algorithms. STOC Russell Impagliazzo, Noam Nisan, Avi Wigderson
1994	A*	`conf`	Upper and Lower Bounds for Tree-Like Cutting Planes Proofs LICS Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart
1993	J	`jnl`	Exponential Lower Bounds for the Pigeonhole Principle. Comput. Complex. Toniann Pitassi, Paul Beame, Russell Impagliazzo
1993	A	`conf`	Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. STACS Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski
1993	J	`jnl`	On Dice and Coins: Models of Computation for Random Generation Inf. Comput. David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir
1993	A*	`conf`	Size-depth trade-offs for threshold circuits. STOC Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks
1993	J	`jnl`	The Effect of Random Restrictions on Formula Size. Random Struct. Algorithms Russell Impagliazzo, Noam Nisan
1992	A*	`conf`	Exponential Lower Bounds for the Pigeonhole Principle STOC Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods
1991	A*	`conf`	Communication Complexity Towards Lower Bounds on Circuit Depth FOCS Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jirí Sgall
1991	A*	`conf`	Computing Planar Intertwines FOCS Arvind Gupta, Russell Impagliazzo
1990	A*	`conf`	No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random FOCS Russell Impagliazzo, Leonid A. Levin
1990	A*	`conf`	Security Preserving Amplification of Hardness FOCS Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman
1989	A*	`conf`	Decision Versus Search Problems in Super-Polynomial Time FOCS Russell Impagliazzo, Gábor Tardos
1989	A*	`conf`	Efficient Cryptographic Schemes Provably as Secure as Subset Sum FOCS Russell Impagliazzo, Moni Naor
1989	A*	`conf`	How to Recycle Random Bits FOCS Russell Impagliazzo, David Zuckerman
1989	A*	`conf`	Limits on the Provable Consequences of One-Way Permutations STOC Russell Impagliazzo, Steven Rudich
1989	A*	`conf`	On Dice and Coins: Models of Computation for Random Generation. ICALP David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir
1989	A*	`conf`	One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract) FOCS Russell Impagliazzo, Michael Luby
1989	A*	`conf`	Pseudo-random Generation from one-way functions (Extended Abstracts) STOC Russell Impagliazzo, Leonid A. Levin, Michael Luby
1988	—	`conf`	Decision trees and downward closures. SCT Russell Impagliazzo, Moni Naor
1988	A*	`conf`	Limits on the Provable Consequences of One-way Permutations. CRYPTO Russell Impagliazzo, Steven Rudich
1987	A*	`conf`	Direct Minimum-Knowledge Computations. CRYPTO Russell Impagliazzo, Moti Yung
1987	A*	`conf`	Generic Oracles and Oracle Classes (Extended Abstract) FOCS Manuel Blum, Russell Impagliazzo