Russell Impagliazzo
#16,823
Most Influential Person Now
American computer scientist
Russell Impagliazzo's AcademicInfluence.com Rankings
Russell Impagliazzocomputer-science Degrees
Computer Science
#1291
World Rank
#1334
Historical Rank
#660
USA Rank
Database
#3899
World Rank
#4056
Historical Rank
#664
USA Rank
Download Badge
Computer Science
Russell Impagliazzo's Degrees
- PhD Computer Science University of California, Berkeley
- Bachelors Mathematics University of California, Berkeley
Similar Degrees You Can Earn
Why Is Russell Impagliazzo Influential?
(Suggest an Edit or Addition)According to Wikipedia, Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory. Education Impagliazzo received a BA in mathematics from Wesleyan University. He obtained a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum. He joined the faculty of UCSD in 1989, having been a postdoc there from 1989 to 1991.
Russell Impagliazzo's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- A Pseudorandom Generator from any One-way Function (1999) (1534)
- On the (im)possibility of obfuscating programs (2001) (1429)
- Which problems have strongly exponential complexity? (1998) (1385)
- Complexity of k-SAT (1999) (1217)
- Designated Verifier Proofs and Their Applications (1996) (866)
- Pseudo-random generation from one-way functions (1989) (663)
- Limits on the provable consequences of one-way permutations (1988) (648)
- P = BPP if E requires exponential circuits: derandomizing the XOR lemma (1997) (560)
- Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds (2003) (515)
- How to recycle random bits (1989) (400)
- One-way functions are essential for complexity based cryptography (1989) (397)
- Using the Groebner basis algorithm to find proofs of unsatisfiability (1996) (368)
- A personal view of average-case complexity (1995) (289)
- Efficient cryptographic schemes provably as secure as subset sum (1989) (289)
- Hard-core distributions for somewhat hard problems (1995) (276)
- Exponential lower bounds for the pigeonhole principle (1992) (252)
- In search of an easy witness: exponential time vs. probabilistic polynomial time (2001) (218)
- Lower bounds on Hilbert's Nullstellensatz and propositional proofs (1994) (215)
- Pseudorandomness for network algorithms (1994) (201)
- Construction of a pseudo-random generator from any one-way function (1989) (201)
- Extracting randomness using few independent sources (2004) (198)
- Pseudo-random Generation from one-way functions (Extended Abstracts) (1989) (180)
- Randomness vs. time: de-randomization under a uniform assumption (1998) (175)
- The relative complexity of NP search problems (1995) (168)
- No better ways to generate hard NP instances than picking uniformly at random (1990) (159)
- Near Optimal Separation Of Tree-Like And General Resolution (2004) (154)
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm (1999) (151)
- The Complexity of Satisfiability of Small Depth Circuits (2009) (150)
- Generic oracles and oracle classes (1987) (145)
- Direct Minimum-Knowledge Computations (1987) (141)
- Does parallel repetition lower the error in computationally sound protocols? (1997) (137)
- A duality between clause width and clause density for SAT (2006) (128)
- Security preserving amplification of hardness (1990) (123)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes (1999) (117)
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility (2016) (107)
- Random Cnf’s are Hard for the Polynomial Calculus (1999) (102)
- Switching lemma for small restrictions and lower bounds for k-DNF resolution (2002) (99)
- A satisfiability algorithm for AC0 (2012) (94)
- P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma (2002) (94)
- A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion (1999) (92)
- Upper and lower bounds for tree-like cutting planes proofs (1994) (89)
- Constructive Proofs of Concentration Bounds (2010) (89)
- Communication complexity towards lower bounds on circuit depth (1991) (88)
- Pseudorandomness from Shrinkage (2012) (88)
- The complexity of unique k-SAT: an isolation lemma for k-CNFs (2003) (86)
- A Satisfiability Algorithm for AC$^0$ (2011) (84)
- Logics for reasoning about cryptographic constructions (2003) (83)
- Uniform direct product theorems: simplified, optimized, and derandomized (2008) (83)
- Learning Algorithms from Natural Proofs (2016) (80)
- How to Forget a Secret (1999) (80)
- Size-Depth Tradeoffs for Threshold Circuits (1997) (74)
- A lower bound for DLL algorithms for k-SAT (preliminary version) (2000) (74)
- Limitations of Noisy Reversible Computation (1996) (71)
- Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space (2012) (65)
- Extractors and pseudo-random generators with optimal seed length (2000) (64)
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (1997) (64)
- The Effect of Random Restrictions on Formula Size (1993) (61)
- AM with Multiple Merlins (2014) (60)
- Models of Greedy Algorithms for Graph Problems (2004) (58)
- Decision trees and downward closures (1988) (58)
- Complexity of kSAT (2007) (58)
- Toward a Model for Backtracking and Dynamic Programming (2005) (58)
- New direct-product testers and 2-query PCPs (2009) (53)
- Reducing the complexity of reductions (1997) (53)
- Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification (2006) (52)
- Hill-climbing finds random planted bisections (2001) (49)
- Near-optimal conversion of hardness into pseudo-randomness (1999) (49)
- Completeness for First-order Properties on Sparse Structures with Algorithmic Applications (2017) (48)
- A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits (2012) (46)
- Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT (2012) (41)
- Formula Caching in DPLL (2010) (41)
- 0-1 Integer Linear Programming with a Linear Number of Constraints (2014) (40)
- On the Complexity of Succinct Zero-Sum Games (2005) (39)
- Memoization and DPLL: formula caching proof systems (2003) (37)
- Chernoff-Type Direct Product Theorems (2007) (36)
- Decision versus search problems in super-polynomial time (1989) (36)
- Homogenization and the polynomial calculus (2003) (31)
- Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations (2003) (30)
- Communication Complexity with Synchronized Clocks (2010) (30)
- The Power of Natural Properties as Oracles (2018) (29)
- Anonymous credentials with biometrically-enforced non-transferability (2003) (29)
- Size-depth trade-offs for threshold circuits (1993) (26)
- Relativized Separations of Worst-Case and Average-Case Complexities for NP (2011) (26)
- An Entropic Proof of Chang's Inequality (2012) (26)
- AC0[p] Lower Bounds against MCSP via the Coin Problem (2019) (25)
- The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs (2007) (25)
- Towards an analysis of local optimization algorithms (1996) (23)
- A direct product theorem (1994) (23)
- Go with the winners for graph bisection (1998) (22)
- Generic Oracles and Oracle Classes (Extended Abstract) (1987) (22)
- Statistical Machine Learning for Large-Scale Optimization (2000) (21)
- Reducing The Seed Length In The Nisan-Wigderson Generator* (2006) (20)
- An axiomatic approach to algebrization (2009) (19)
- Improved depth lower bounds for small distance connectivity (1995) (19)
- Stabbing Planes (2017) (19)
- Fourier Concentration from Shrinkage (2014) (19)
- Hardness as randomness: a survey of universal derandomization (2003) (19)
- Relativizing versus Nonrelativizing Techniques: The Role of Local Checkability (1992) (18)
- On Dice and Coins: Models of Computation for Random Generation (1989) (17)
- Subexponential Circuits : Derandomizing the XOR Lemma (2003) (16)
- A zero one law for RP (2003) (15)
- A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory (1997) (15)
- A Note on Conservativity Relations among Bounded Arithmetic Theories (2002) (15)
- Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits (2012) (15)
- A Stronger Model of Dynamic Programming Algorithms (2011) (15)
- Strong ETH holds for regular resolution (2013) (15)
- Improved Algorithms for Unique Games via Divide and Conquer (2010) (15)
- Finding Heavy Hitters from Lossy or Noisy Data (2013) (14)
- Hardness Amplification for Non-Commutative Arithmetic Circuits (2018) (14)
- Cryptography and Computer Security (2003) (13)
- Tighter Connections between Derandomization and Circuit Lower Bounds (2015) (13)
- Security Amplification for InteractiveCryptographic Primitives (2009) (13)
- Reproducibility in learning (2022) (12)
- Orthogonal Vectors is hard for first-order properties on sparse graphs (2016) (12)
- Counting axioms do not polynomially simulate counting gates (2001) (12)
- Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution (1993) (11)
- On the Exact Complexity of Evaluating Quantified k-CNF (2010) (11)
- Online Algorithms to Minimize Resource Reallocations and Network Communication (2006) (10)
- On the power and limitations of branch and cut (2021) (9)
- Computing planar intertwines (1991) (9)
- Empirical and analytic approaches to understanding local search heuristics (2001) (8)
- Pseudorandomness when the odds are against you (2016) (7)
- Security-preserving hardness-amplification for any regular one-way function (1999) (7)
- Boosting in the Presence of Massart Noise (2021) (7)
- The Surprising Power of Constant Depth Algebraic Proofs (2020) (7)
- Agnostic Learning from Tolerant Natural Proofs (2017) (6)
- Resolution complexity of independent sets in random graphs (2001) (6)
- Homogenization and the Polynominal Calculus (2000) (6)
- Algorithms from Natural Lower Bounds (2016) (6)
- The Reachability Problem for Finite Cellular Automata (1995) (5)
- The Fine-Grained Complexity of Strengthenings of First-Order Logic (2019) (5)
- Bounding the Size of Planar Intertwines (1997) (5)
- On the pseudo-deterministic query complexity of NP search problems (2021) (4)
- Can every randomized algorithm be derandomized? (2006) (4)
- Proofs of membership vs. proofs of knowledge (1998) (4)
- Universal languages and the power of diagonalization (2003) (4)
- The Fine-Grained Complexity of Multi-Dimensional Ordering Properties (2022) (4)
- Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata (1994) (4)
- A zero one law for (2003) (4)
- Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity (2018) (4)
- Decision trees and downward closures* (Extended Abstract) (1988) (4)
- A zero-one law for RP and derandomization of AM if NP is not small (2009) (4)
- New separations in propositional proof complexity (2003) (3)
- Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems (2001) (3)
- Computational Complexity Since 1980 (2005) (3)
- Half-duplex communication complexity (2018) (3)
- Does Looking Inside a Circuit Help? (2017) (3)
- Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization (2023) (2)
- Complexity aspects of knowledge representation (1996) (2)
- Comparing computational entropies below majority (or: When is the dense model theorem false?) (2020) (1)
- Towards Time-Space Lower Bounds On Branching Programs (2016) (1)
- Algorithmic Dense Model Theorems and Weak Regularity (2009) (1)
- Exact Complexity and Satisfiability - (Invited Talk) (2013) (1)
- Memoization and DPLL (2003) (1)
- Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations (2002) (1)
- Experimentally Determining Regions of Related Solutions for GraphBisection (1)
- Secure group communication: self-healing key distribution and nontransferable anonymous credentials (2003) (1)
- On the average-case complexity of the reversibility problem for finite cellular automata (1994) (1)
- The Second Part of the next Claim Follows from a Standard Application of Chernoo Bounds. B General Commodity Testing (1999) (1)
- A note on onservativity relations among bounded arithmeti theories (2017) (1)
- Lower bounds for Polynomial Calculus with extension variables over finite fields (2022) (1)
- Using Hard Problems to Derandomize Algorithms: An Incomplete Survey (1997) (1)
- Randomized Approximation of MAX-CUT (2017) (0)
- Statistical Machine Learning for Large-Scale Optimization Contributors (0)
- Optimal Seperation of Treelike and General Resolution Preliminary Version (1999) (0)
- Algorithmic Topics in Bioinformatics : The Partial Digest Problem ( Paper for CSE 202 : Prof (2004) (0)
- The Reachability problem for nite cellular automata (2004) (0)
- The sacrifice precision method (2012) (0)
- Computational Complexity ( 10 w 5028 ) (2011) (0)
- Mathematisches Forschungsinstitut Oberwolfach Proving Hard-core Predicates Using List Decoding Proving Integrality Gaps without Knowing the Linear Program How to Go beyond the Black-box Simulation Barrier Derandomization in Cryptography Formula Caching Proof Systems Algebras of Minimal Rank over Arb (2003) (0)
- Limitations of Noisy Reversible (1996) (0)
- Simultaneous Secrecy and Reliability Amplification for a General Channel Model (2016) (0)
- Session details: Session 1A (2007) (0)
- Hardcore Measures , Dense Models and Low Complexity Approximations (2017) (0)
- UTIME Easy-witness Lemma & Some Consequences (2019) (0)
- 08w5094 Analytic Tools in Computational Complexity (2008) (0)
- Near-Optimal Separation of Treelike andGeneral (2000) (0)
- CSE 200 HW 2 Solutions (2016) (0)
- Ja n 20 14 AM with Multiple Merlins (2018) (0)
- On the Exact Complexity of Evaluating Quantified k-CNF (2012) (0)
- Session details: Session 14A (2005) (0)
- Infinitely-Often Universal Languages and Diagonalization (2006) (0)
- TFNP Characterizations of Proof Systems and Monotone Circuits (2022) (0)
- Lifting for Constant-Depth Circuits and Applications to MCSP (2021) (0)
- Session details: Session 12A (2005) (0)
- Advances in Complexity Theory (2004) (0)
This paper list is powered by the following services:
Other Resources About Russell Impagliazzo
What Schools Are Affiliated With Russell Impagliazzo?
Russell Impagliazzo is affiliated with the following schools:
