Russell Impagliazzo

ScholarGPS® ID: 34599322876892

Affiliation

University of California, San Diego, San Diego, United States

Affiliation History

Field

Engineering and Computer Science

Discipline

Computer Science

Top Specialties

Metrics Summary

Publication Count

155

Predicted Citations

15,694

Predicted h-index

Ranking

Publications and Citation History

Publications based on Top Specialties

Types of Publication

Publications
Books
Patents
NIH/NSF

Add Delete
The Power of Natural Properties as Oracles (journal article) Impagliazzo, Russell \| Kabanets, Valentine \| Volkovich, Ilya computational complexity, volume 32, issue 2 (2023). 10.1007/s00037-023-00241-0 Cited by (2) \| Cite \| Source
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization (conference) Bun, Mark \| Gaboardi, Marco \| Hopkins, Max \| Impagliazzo, Russell \| Lei, Rex \| Pitassi, Toniann \| Sivakumar, Satchit \| Sorrell, Jessica STOC '23: 55th Annual ACM Symposium on Theory of Computing (2023) Orlando FL USA 10.1145/3564246.3585246 Cited by (1) \| Cite \| Source
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties (journal article) An, Haozhe \| Gurumukhani, Mohit \| Impagliazzo, Russell \| Jaber, Michael \| Künnemann, Marvin \| Parga Nina, Maria Paula Algorithmica, volume 84, issue 11, pages 3156-3191 (2022). 10.1007/s00453-022-01014-x Cite \| Source
Reproducibility in learning (conference) Impagliazzo, Russell \| Lei, Rex \| Pitassi, Toniann \| Sorrell, Jessica STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing (2022) Rome Italy 10.1145/3519935.3519973 Cited by (6) \| Cite \| Source
The Surprising Power of Constant Depth Algebraic Proofs (conference) Impagliazzo, Russell \| Mouli, Sasank \| Pitassi, Toniann LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science (2020) Saarbrücken Germany 10.1145/3373718.3394754 Cited by (4) \| Cite \| Source
Pseudorandomness from Shrinkage (journal article) Impagliazzo, Russell \| Meka, Raghu \| Zuckerman, David Journal of the ACM, volume 66, issue 2, pages 1-16 (2019). 10.1145/3230630 Cited by (8) \| Cite \| Source
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications (journal article) Gao, Jiawei \| Impagliazzo, Russell \| Kolokolova, Antonina \| Williams, Ryan ACM Transactions on Algorithms, volume 15, issue 2, pages 1-35 (2019). 10.1145/3196275 Cited by (11) \| Cite \| Source
The power of natural properties as oracles (conference) Impagliazzo, Russell \| Kabanets, Valentine \| Volkovich, Ilya Conference on Computational Complexity (2018) 10.4230/LIPIcs.CCC.2018.7 Cited by (10) \| Cite \| Source
Hardness amplification for non-commutative arithmetic circuits (conference) Carmosino, Marco L. \| Impagliazzo, Russell \| Lovett, Shachar \| Mihajlin, Ivan Conference on Computational Complexity (2018) 10.4230/LIPIcs.CCC.2018.12 Cited by (4) \| Cite \| Source
Fourier Concentration from Shrinkage (journal article) Impagliazzo, Russell \| Kabanets, Valentine computational complexity, volume 26, issue 1, pages 275-321 (2017). 10.1007/s00037-016-0134-y Cited by (2) \| Cite \| Source
Agnostic Learning from Tolerant Natural Proofs. (conference) Carmosino, Marco L. \| Impagliazzo, Russell \| Kabanets, Valentine \| Kolokolova, Antonina International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2017) 10.4230/LIPIcs.APPROX-RANDOM.2017.35 Cited by (2) \| Cite \| Source
Does Looking Inside a Circuit Help (conference) Impagliazzo, Russell \| Kabanets, Valentine \| Kolokolova, Antonina \| McKenzie, Pierre \| Romani, Shadab Mathematical Foundations of Computer Science (2017) 10.4230/LIPIcs.MFCS.2017.1 Cite \| Source
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications (conference) Gao, Jiawei \| Impagliazzo, Russell \| Kolokolova, Antonina \| Williams, Ryan Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (2017) 10.1137/1.9781611974782.141 Cited by (8) \| Cite \| Source \| Open Access
Learning algorithms from natural proofs (conference) Carmosino, Marco L. \| Impagliazzo, Russell \| Kabanets, Valentine \| Kolokolova, Antonina Conference on Computational Complexity (2016) 10.4230/LIPIcs.CCC.2016.10 Cited by (25) \| Cite \| Source
Pseudorandomness when the odds are against you (conference) Artemenko, Sergei \| Impagliazzo, Russell \| Kabanets, Valentine \| Shaltiel, Ronen Conference on Computational Complexity (2016) 10.4230/LIPIcs.CCC.2016.9 Cited by (3) \| Cite \| Source
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility (conference) Carmosino, Marco L. \| Gao, Jiawei \| Impagliazzo, Russell \| Mihajlin, Ivan \| Paturi, Ramamohan \| Schneider, Stefan ITCS'16: Innovations in Theoretical Computer Science (2016) Cambridge Massachusetts USA 10.1145/2840728.2840746 Cited by (45) \| Cite \| Source \| Open Access
Simultaneous Secrecy and Reliability Amplification for a General Channel Model (book chapter) In Theory of Cryptography Impagliazzo, Russell \| Jaiswal, Ragesh \| Kabanets, Valentine \| Kapron, Bruce M. \| King, Valerie \| Tessaro, Stefano Springer Berlin Heidelberg (2016) 10.1007/978-3-662-53641-4_10 Cite \| Source
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space (journal article) Beame, Paul \| Beck, Chris \| Impagliazzo, Russell SIAM Journal on Computing, volume 45, issue 4, pages 1612-1645 (2016). 10.1137/130914085 Cited by (9) \| Cite \| Source \| Open Access
Tighter Connections between Derandomization and Circuit Lower Bounds (conference) Carmosino, Marco L. \| Impagliazzo, Russell \| Kabanets, Valentine \| Kolokolova, Antonina International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2015) 10.4230/LIPIcs.APPROX-RANDOM.2015.645 Cited by (4) \| Cite \| Source
AM with Multiple Merlins (conference) Aaronson, Scott \| Impagliazzo, Russell \| Moshkovitz, Dana 2014 IEEE Conference on Computational Complexity (CCC) (2014) Vancouver, BC, Canada 10.1109/CCC.2014.13 Cited by (23) \| Cite \| Source \| Open Access

Title	Investigators	Year	Expiration	Amount
AF: SMALL: Finding Models of Data and Mathematical Objects	Impagliazzo, Russell \| Lovett, Shachar	07-01-2019	06-30-2022	$499,999
AF: Large: Collaborative Research: Exploiting Duality between Meta-Algorithms and Complexity	Paturi, Ramamohan \| Impagliazzo, Russell \| Buss, Samuel	07-01-2012	06-30-2017	$1,250,000
CDI Type II: Pseudorandomness	Wigderson, Avi \| Bourgain, Jean \| Sarnak, Peter \| Impagliazzo, Russell	10-01-2008	09-30-2013	$1,750,000
CT-ISG: Amplifying both security and reliability	Impagliazzo, Russell	08-01-2007	07-31-2011	$398,600
Duality between Complexity and Algorithms	Paturi, Ramamohan \| Impagliazzo, Russell	07-15-2005	06-30-2008	$201,647
ITR: Cryptography: from user needs to protocol design	Micciancio, Daniele \| Impagliazzo, Russell	08-15-2003	07-31-2006	$300,000
Quantifying Intractability and the Complexity of Heuristics	Paturi, Ramamohan \| Impagliazzo, Russell	07-01-2001	09-30-2004	$351,711
CISE Research Infrastructure: The UCSD Active Web	Ferrante, Jeanne \| Pasquale, Joseph \| Belew, Richard \| Impagliazzo, Russell \| Rangan, Venkat	09-01-1998	08-31-2005	$1,499,969
Empirical Analysis of Search Spaces Using Population-Based Sampling	Belew, Richard \| Impagliazzo, Russell	08-15-1998	07-31-2000	$125,043
Developing a Theory of Heuristics	Paturi, Ramamohan \| Impagliazzo, Russell	07-15-1998	06-30-2001	$194,616
NSF Young Investigator: Small Depth Boolean Circuits and Complexity - Theoretic Cryptography	Impagliazzo, Russell	09-15-1992	08-31-1997	$155,000