Russell Impagliazzo

Affiliations:
  • University of California, San Diego, USA


According to our database1, Russell Impagliazzo authored at least 158 papers between 1987 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
The Power of Natural Properties as Oracles.
Comput. Complex., December, 2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.
Electron. Colloquium Comput. Complex., 2023

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.
Proceedings of the Approximation, 2023

2022
Lower bounds for Polynomial Calculus with extension variables over finite fields.
Electron. Colloquium Comput. Complex., 2022

TFNP Characterizations of Proof Systems and Monotone Circuits.
Electron. Colloquium Comput. Complex., 2022

The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.
Algorithmica, 2022

Reproducibility in learning.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021
On the Power and Limitations of Branch and Cut.
Electron. Colloquium Comput. Complex., 2021

Lifting for Constant-Depth Circuits and Applications to MCSP.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Boosting in the Presence of Massart Noise.
Proceedings of the Conference on Learning Theory, 2021

On the Pseudo-Deterministic Query Complexity of NP Search Problems.
Proceedings of the 36th Computational Complexity Conference, 2021

2020
Comparing computational entropies below majority (or: When is the dense model theorem false?).
Electron. Colloquium Comput. Complex., 2020

2019
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications.
ACM Trans. Algorithms, 2019

Pseudorandomness from Shrinkage.
J. ACM, 2019

The Surprising Power of Constant Depth Algebraic Proofs.
Electron. Colloquium Comput. Complex., 2019

AC0[p] Lower Bounds against MCSP via the Coin Problem.
Electron. Colloquium Comput. Complex., 2019

The Fine-Grained Complexity of Strengthenings of First-Order Logic.
Electron. Colloquium Comput. Complex., 2019

UTIME Easy-witness Lemma & Some Consequences.
Electron. Colloquium Comput. Complex., 2019

AC<sup>0</sup>[p] Lower Bounds Against MCSP via the Coin Problem.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Half-duplex communication complexity.
Electron. Colloquium Comput. Complex., 2018

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity.
Electron. Colloquium Comput. Complex., 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.
Electron. Colloquium Comput. Complex., 2018

2017
Does Looking Inside a Circuit Help?
Electron. Colloquium Comput. Complex., 2017

Stabbing Planes.
Electron. Colloquium Comput. Complex., 2017

Fourier Concentration from Shrinkage.
Comput. Complex., 2017

Agnostic Learning from Tolerant Natural Proofs.
Proceedings of the Approximation, 2017

2016
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
SIAM J. Comput., 2016

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.
IACR Cryptol. ePrint Arch., 2016

Orthogonal Vectors is hard for first-order properties on sparse graphs.
Electron. Colloquium Comput. Complex., 2016

Algorithms from Natural Lower Bounds.
Electron. Colloquium Comput. Complex., 2016

Pseudorandomness when the odds are against you.
Electron. Colloquium Comput. Complex., 2016

Learning Algorithms from Natural Proofs.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility.
Electron. Colloquium Comput. Complex., 2015

Tighter Connections between Derandomization and Circuit Lower Bounds.
Proceedings of the Approximation, 2015

2014
An Entropic Proof of Chang's Inequality.
SIAM J. Discret. Math., 2014

0-1 Integer Linear Programming with a Linear Number of Constraints.
Electron. Colloquium Comput. Complex., 2014

AM with Multiple Merlins.
Electron. Colloquium Comput. Complex., 2014

2013
On the Exact Complexity of Evaluating Quantified <i>k</i> -CNF.
Algorithmica, 2013

Strong ETH holds for regular resolution.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Exact Complexity and Satisfiability - (Invited Talk).
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Finding Heavy Hitters from Lossy or Noisy Data.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
On the (im)possibility of obfuscating programs.
J. ACM, 2012

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits.
Electron. Colloquium Comput. Complex., 2012

A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits
CoRR, 2012

A satisfiability algorithm for AC<sup>0</sup>.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT.
Proceedings of the 27th Conference on Computational Complexity, 2012

2011
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
Electron. Colloquium Comput. Complex., 2011

A Satisfiability Algorithm for AC$^0$
CoRR, 2011

Toward a Model for Backtracking and Dynamic Programming.
Comput. Complex., 2011

A Stronger Model of Dynamic Programming Algorithms.
Algorithmica, 2011

Relativized Separations of Worst-Case and Average-Case Complexities for NP.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010
Constructive Proofs of Concentration Bounds.
Electron. Colloquium Comput. Complex., 2010

Improved Algorithms for Unique Games via Divide and Conquer.
Electron. Colloquium Comput. Complex., 2010

Random Cnf's are Hard for the Polynomial Calculus.
Comput. Complex., 2010

Communication Complexity with Synchronized Clocks.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification.
SIAM J. Comput., 2009

Chernoff-Type Direct Product Theorems.
J. Cryptol., 2009

A zero-one law for RP and derandomization of AM if NP is not small.
Inf. Comput., 2009

New Direct-Product Testers and 2-Query PCPs.
Electron. Colloquium Comput. Complex., 2009

Toward a Model for Backtracking and Dynamic Programming.
Electron. Colloquium Comput. Complex., 2009

Models of Greedy Algorithms for Graph Problems.
Algorithmica, 2009

Security Amplification for InteractiveCryptographic Primitives.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

The Complexity of Satisfiability of Small Depth Circuits.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

An Axiomatic Approach to Algebrization.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

2008
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.
J. Comput. Syst. Sci., 2008

Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized.
Electron. Colloquium Comput. Complex., 2008

On the Complexity of Succinct Zero-Sum Games.
Comput. Complex., 2008

2007
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.
Comput. Complex., 2007

2006
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.
ACM Trans. Comput. Log., 2006

Extracting Randomness Using Few Independent Sources.
SIAM J. Comput., 2006

Logics for reasoning about cryptographic constructions.
J. Comput. Syst. Sci., 2006

Infinitely-Often Universal Languages and Diagonalization.
Electron. Colloquium Comput. Complex., 2006

Formula Caching in DPLL.
Electron. Colloquium Comput. Complex., 2006

Reducing The Seed Length In The Nisan-Wigderson Generator.
Comb., 2006

Can every randomized algorithm be derandomized?
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

A Duality between Clause Width and Clause Density for SAT.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Online Algorithms to Minimize Resource Reallocations and Network Communication.
Proceedings of the Approximation, 2006

2005
Computational Complexity Since 1980.
Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

2004
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.
SIAM J. Comput., 2004

Near Optimal Separation Of Tree-Like And General Resolution.
Comb., 2004

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.
Comput. Complex., 2004

2003
Hardness as randomness: a survey of universal derandomization
CoRR, 2003

Anonymous credentials with biometrically-enforced non-transferability.
Proceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, 2003

Universal Languages and the Power of Diagonalization.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

A zero one law for RP.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Memoization and DPLL: Formula Caching Proof Systems.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
A Note on Conservativity Relations among Bounded Arithmetic Theories.
Math. Log. Q., 2002

In search of an easy witness: exponential time vs. probabilistic polynomial time.
J. Comput. Syst. Sci., 2002

Homogenization and the polynomial calculus.
Comput. Complex., 2002

Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001
Randomness vs Time: Derandomization under a Uniform Assumption.
J. Comput. Syst. Sci., 2001

Which Problems Have Strongly Exponential Complexity?
J. Comput. Syst. Sci., 2001

On the Complexity of k-SAT.
J. Comput. Syst. Sci., 2001

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.
J. Comput. Syst. Sci., 2001

Communication complexity towards lower bounds on circuit depth.
Comput. Complex., 2001

Reducing the complexity of reductions.
Comput. Complex., 2001

Hill-climbing finds random planted bisections.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems.
Proceedings of the Approximation, 2001

Counting Axioms Do Not Polynomially Simulate Counting Gates.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

On the (Im)possibility of Obfuscating Programs.
Proceedings of the Advances in Cryptology, 2001

Resolution Complexity of Independent Sets in Random Graphs.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
Extractors and pseudo-random generators with optimal seed length
Electron. Colloquium Comput. Complex., 2000

Near-Optimal Separation of Treelike and General Resolution
Electron. Colloquium Comput. Complex., 2000

A lower bound for DLL algorithms for <i>k</i>-SAT (preliminary version).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Homogenization and the Polynominal Calculus.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
A Pseudorandom Generator from any One-way Function.
SIAM J. Comput., 1999

A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion.
IACR Cryptol. ePrint Arch., 1999

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.
Comput. Complex., 1999

Security-Preserving Hardness-Amplification for Any Regular One-Way Function.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

How to Forget a Secret.
Proceedings of the STACS 99, 1999

Near-Optimal Conversion of Hardness into Pseudo-Randomness.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
The Relative Complexity of NP Search Problems.
J. Comput. Syst. Sci., 1998

Improved Depth Lower Bounds for Small Distance Connectivity.
Comput. Complex., 1998

Go with the Winners for Graph Bisection.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Randomness vs. Time: De-Randomization under a Uniform Assumption.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Proofs of Membership vs. Proofs of Knowledge.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
Bounding the Size of Planar Intertwines.
SIAM J. Discret. Math., 1997

Size-Depth Tradeoffs for Threshold Circuits.
SIAM J. Comput., 1997

A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory.
Inf. Comput., 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm
Electron. Colloquium Comput. Complex., 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Comput. Complex., 1997

<i>P = BPP</i> if <i>E</i> Requires Exponential Circuits: Derandomizing the XOR Lemma.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Using Hard Problems to Derandomize Algorithms: An Incomplete Survey.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Does Parallel Repetition Lower the Error in Computationally Sound Protocols?
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Efficient Cryptographic Schemes Provably as Secure as Subset Sum.
J. Cryptol., 1996

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.
J. Comput. Syst. Sci., 1996

Towards an Analysis of Local Optimization Algorithms.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Designated Verifier Proofs and Their Applications.
Proceedings of the Advances in Cryptology, 1996

1995
The Reachability Problem for Finite Cellular Automata.
Inf. Process. Lett., 1995

Hard-Core Distributions for Somewhat Hard Problems.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Improved Depth Lower Vounds for Small Distance Connectivity.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

A Personal View of Average-Case Complexity.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
Pseudorandomness for network algorithms.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Upper and Lower Bounds for Tree-Like Cutting Planes Proofs
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

A Direct Product Theorem.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata.
Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993
On Dice and Coins: Models of Computation for Random Generation
Inf. Comput., June, 1993

The Effect of Random Restrictions on Formula Size.
Random Struct. Algorithms, 1993

Exponential Lower Bounds for the Pigeonhole Principle.
Comput. Complex., 1993

Size-depth trade-offs for threshold circuits.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
Exponential Lower Bounds for the Pigeonhole Principle
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
Computing Planar Intertwines
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Security Preserving Amplification of Hardness
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Limits on the Provable Consequences of One-Way Permutations
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Pseudo-random Generation from one-way functions (Extended Abstracts)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

How to Recycle Random Bits
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Decision Versus Search Problems in Super-Polynomial Time
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
Decision trees and downward closures.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Generic Oracles and Oracle Classes (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Direct Minimum-Knowledge Computations.
Proceedings of the Advances in Cryptology, 1987


  Loading...