Russell Impagliazzo

ORCID

Publication Activity (10 Years)

Years Active: 1987-2024
Publications (10 Years): 58

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

Computational Complexity Conference

ITCS

Publications

Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye
The Computational Complexity of Factored Graphs. CoRR (2024)
Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye
Replicability in High Dimensional Statistics. CoRR (2024)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Comput. Complex. 32 (2) (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM (2023)
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC (2023)
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 (2023)
Sam Buss, Noah Fleming, Russell Impagliazzo
TFNP Characterizations of Proof Systems and Monotone Circuits. ITCS (2023)
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)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. (2023)
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) (2022)
Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell
Reproducibility in Learning. CoRR (2022)
Sam Buss, Noah Fleming, Russell Impagliazzo
TFNP Characterizations of Proof Systems and Monotone Circuits. Electron. Colloquium Comput. Complex. (2022)
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
Lower bounds for Polynomial Calculus with extension variables over finite fields. Electron. Colloquium Comput. Complex. (2022)
Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell
Reproducibility in learning. STOC (2022)
Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
Boosting in the Presence of Massart Noise. COLT (2021)
Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Lifting for Constant-Depth Circuits and Applications to MCSP. ICALP (2021)
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 (2021)
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. 28 (2021)
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. Computational Complexity Conference (2021)
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam
On the Pseudo-Deterministic Query Complexity of NP Search Problems. Computational Complexity Conference (2021)
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)
Russell Impagliazzo, Sam McGuire
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). ITCS (2021)
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
Boosting in the Presence of Massart Noise. CoRR (2021)
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
The Surprising Power of Constant Depth Algebraic Proofs. LICS (2020)
Russell Impagliazzo, Sam McGuire
Comparing computational entropies below majority (or: When is the dense model theorem false?). Electron. Colloquium Comput. Complex. 27 (2020)
Russell Impagliazzo, Sam McGuire
Comparing computational entropies below majority (or: When is the dense model theorem false?). CoRR (2020)
Anant Dhayal, Russell Impagliazzo
UTIME Easy-witness Lemma & Some Consequences. Electron. Colloquium Comput. Complex. 26 (2019)
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
The Surprising Power of Constant Depth Algebraic Proofs. Electron. Colloquium Comput. Complex. 26 (2019)
Jiawei Gao, Russell Impagliazzo
The Fine-Grained Complexity of Strengthenings of First-Order Logic. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal
[p] Lower Bounds Against MCSP via the Coin Problem. ICALP (2019)
Russell Impagliazzo, Raghu Meka, David Zuckerman
Pseudorandomness from Shrinkage. J. ACM 66 (2) (2019)
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. 26 (2019)
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms 15 (2) (2019)
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
Stabbing Planes. ITCS (2018)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Computational Complexity Conference (2018)
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal
Half-Duplex Communication Complexity. ISAAC (2018)
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Half-duplex communication complexity. Electron. Colloquium Comput. Complex. 25 (2018)
Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
Hardness Amplification for Non-Commutative Arithmetic Circuits. Computational Complexity Conference (2018)
Marco Carmosino, Russell Impagliazzo, Manuel Sabin
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. Electron. Colloquium Comput. Complex. 25 (2018)
Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. ICALP (2018)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM (2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
Does Looking Inside a Circuit Help?. MFCS (2017)
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. SODA (2017)
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
Stabbing Planes. Electron. Colloquium Comput. Complex. 24 (2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. 24 (2017)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. 24 (2017)
Russell Impagliazzo, Valentine Kabanets
Fourier Concentration from Shrinkage. Comput. Complex. 26 (1) (2017)
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
Stabbing Planes. CoRR (2017)
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
Pseudorandomness When the Odds are Against You. Computational Complexity Conference (2016)
Jiawei Gao, Russell Impagliazzo
Orthogonal Vectors is hard for first-order properties on sparse graphs. Electron. Colloquium Comput. Complex. 23 (2016)
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel
Pseudorandomness when the odds are against you. Electron. Colloquium Comput. Complex. 23 (2016)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Algorithms from Natural Lower Bounds. Electron. Colloquium Comput. Complex. 23 (2016)
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)
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)
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 (2016)
Paul Beame, Chris Beck, Russell Impagliazzo
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. SIAM J. Comput. 45 (4) (2016)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Learning Algorithms from Natural Proofs. Computational Complexity Conference (2016)
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. 22 (2015)
Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova
Tighter Connections between Derandomization and Circuit Lower Bounds. APPROX-RANDOM (2015)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. 21 (2014)
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
0-1 Integer Linear Programming with a Linear Number of Constraints. Electron. Colloquium Comput. Complex. 21 (2014)
Russell Impagliazzo, Valentine Kabanets
Fourier Concentration from Shrinkage. Computational Complexity Conference (2014)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. Computational Complexity Conference (2014)
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
0-1 Integer Linear Programming with a Linear Number of Constraints. CoRR (2014)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. CoRR (2014)
Russell Impagliazzo, Cristopher Moore, Alexander Russell
An Entropic Proof of Chang's Inequality. SIAM J. Discret. Math. 28 (1) (2014)
Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. FOCS (2013)
Christopher Beck, Russell Impagliazzo
Strong ETH holds for regular resolution. STOC (2013)
Russell Impagliazzo, Ramamohan Paturi
Exact Complexity and Satisfiability - (Invited Talk). IPEC (2013)
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
-CNF. Algorithmica 65 (4) (2013)
Russell Impagliazzo, Valentine Kabanets
Fourier Concentration from Shrinkage. Electron. Colloquium Comput. Complex. 20 (2013)
Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi
Finding Heavy Hitters from Lossy or Noisy Data. APPROX-RANDOM (2013)
Russell Impagliazzo, William Matthews, Ramamohan Paturi
. SODA (2012)
Russell Impagliazzo, Raghu Meka, David Zuckerman
Pseudorandomness from Shrinkage. Electron. Colloquium Comput. Complex. 19 (2012)
Paul Beame, Russell Impagliazzo, Srikanth Srinivasan
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. Computational Complexity Conference (2012)
Russell Impagliazzo, Cristopher Moore, Alexander Russell
An Entropic Proof of Chang's Inequality CoRR (2012)
Paul Beame, Christopher Beck, Russell Impagliazzo
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC (2012)
Chris Beck, Russell Impagliazzo, Shachar Lovett
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Electron. Colloquium Comput. Complex. 19 (2012)
Russell Impagliazzo, Raghu Meka, David Zuckerman
Pseudorandomness from Shrinkage. FOCS (2012)
Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits CoRR (2012)
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) (2012)
Chris Beck, Russell Impagliazzo, Shachar Lovett
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. FOCS (2012)
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. 41 (6) (2012)
Russell Impagliazzo, William Matthews, Ramamohan Paturi
A Satisfiability Algorithm for AC$^0$ CoRR (2011)
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) (2011)
Russell Impagliazzo
Relativized Separations of Worst-Case and Average-Case Complexities for NP. Computational Complexity Conference (2011)
Paul Beame, Chris Beck, Russell Impagliazzo
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electron. Colloquium Comput. Complex. 18 (2011)
Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo
A Stronger Model of Dynamic Programming Algorithms. Algorithmica 60 (4) (2011)
Eli Ben-Sasson, Russell Impagliazzo
Random Cnf's are Hard for the Polynomial Calculus. Comput. Complex. 19 (4) (2010)
Russell Impagliazzo, Valentine Kabanets
Constructive Proofs of Concentration Bounds. APPROX-RANDOM (2010)
Russell Impagliazzo, Valentine Kabanets
Constructive Proofs of Concentration Bounds. Electron. Colloquium Comput. Complex. 17 (2010)
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
-CNF. IPEC (2010)
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
Formula Caching in DPLL. ACM Trans. Comput. Theory 1 (3) (2010)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39 (4) (2010)
Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer
Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex. 17 (2010)
Russell Impagliazzo, Ryan Williams
Communication Complexity with Synchronized Clocks. Computational Complexity Conference (2010)
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets
Chernoff-Type Direct Product Theorems. J. Cryptol. 22 (1) (2009)
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson
New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. 16 (2009)
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
The Complexity of Satisfiability of Small Depth Circuits. IWPEC (2009)

Russell Impagliazzo.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Russell Impagliazzo