Russell Impagliazzo

According to our database, Russell Impagliazzo authored at least 161 papers between 1987 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Lifting to Randomized Parity Decision Trees.

Farzan Byramji, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2024

The Greedy Coin Change Problem.

Shreya Gupta, Boyang Huang, Russell Impagliazzo

CoRR, 2024

The Computational Complexity of Factored Graphs.

Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye

CoRR, 2024

Replicability in High Dimensional Statistics.

Max Hopkins, Russell Impagliazzo, Daniel M. Kane, Sihan Liu, Christopher Ye

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

The Power of Natural Properties as Oracles.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Comput. Complex., December, 2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2023

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.

Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Proceedings of the Approximation, 2023

2022

Lower bounds for Polynomial Calculus with extension variables over finite fields.

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2022

TFNP Characterizations of Proof Systems and Monotone Circuits.

Sam Buss, Noah Fleming, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2022

The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.

Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina

Algorithmica, 2022

Reproducibility in learning.

Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell

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.

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

Electron. Colloquium Comput. Complex., 2021

Lifting for Constant-Depth Circuits and Applications to MCSP.

Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Boosting in the Presence of Massart Noise.

Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos

Proceedings of the Conference on Learning Theory, 2021

On the Pseudo-Deterministic Query Complexity of NP Search Problems.

Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Comparing computational entropies below majority (or: When is the dense model theorem false?).

Russell Impagliazzo, Sam McGuire

Electron. Colloquium Comput. Complex., 2020

2019

Completeness for First-order Properties on Sparse Structures with Algorithmic Applications.

Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams

ACM Trans. Algorithms, 2019

The Surprising Power of Constant Depth Algebraic Proofs.

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2019

AC0[p] Lower Bounds against MCSP via the Coin Problem.

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Electron. Colloquium Comput. Complex., 2019

The Fine-Grained Complexity of Strengthenings of First-Order Logic.

Jiawei Gao, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2019

UTIME Easy-witness Lemma & Some Consequences.

Anant Dhayal, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2019

AC⁰[p] Lower Bounds Against MCSP via the Coin Problem.

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Half-duplex communication complexity.

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Electron. Colloquium Comput. Complex., 2018

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity.

Marco Carmosino, Russell Impagliazzo, Manuel Sabin

Electron. Colloquium Comput. Complex., 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Electron. Colloquium Comput. Complex., 2018

2017

Does Looking Inside a Circuit Help?

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Electron. Colloquium Comput. Complex., 2017

Stabbing Planes.

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Fourier Concentration from Shrinkage.

Russell Impagliazzo, Valentine Kabanets

Comput. Complex., 2017

Agnostic Learning from Tolerant Natural Proofs.

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the Approximation, 2017

2016

Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.

Paul Beame, Chris Beck, Russell Impagliazzo

SIAM J. Comput., 2016

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro

IACR Cryptol. ePrint Arch., 2016

Orthogonal Vectors is hard for first-order properties on sparse graphs.

Jiawei Gao, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2016

Algorithms from Natural Lower Bounds.

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Electron. Colloquium Comput. Complex., 2016

Pseudorandomness when the odds are against you.

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Electron. Colloquium Comput. Complex., 2016

Learning Algorithms from Natural Proofs.

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility.

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider

Electron. Colloquium Comput. Complex., 2015

Tighter Connections between Derandomization and Circuit Lower Bounds.

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the Approximation, 2015

2014

An Entropic Proof of Chang's Inequality.

Russell Impagliazzo, Cristopher Moore, Alexander Russell

SIAM J. Discret. Math., 2014

0-1 Integer Linear Programming with a Linear Number of Constraints.

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

Electron. Colloquium Comput. Complex., 2014

AM with Multiple Merlins.

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2014

2013

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

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Algorithmica, 2013

Strong ETH holds for regular resolution.

Christopher Beck, Russell Impagliazzo

Proceedings of the Symposium on Theory of Computing Conference, 2013

Exact Complexity and Satisfiability - (Invited Talk).

Russell Impagliazzo, Ramamohan Paturi

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.

Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Finding Heavy Hitters from Lossy or Noisy Data.

Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

New Direct-Product Testers and 2-Query PCPs.

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

SIAM J. Comput., 2012

Pseudorandomness from Shrinkage.

Russell Impagliazzo, Raghu Meka, David Zuckerman

Electron. Colloquium Comput. Complex., 2012

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits.

Chris Beck, Russell Impagliazzo, Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits

Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider

CoRR, 2012

A satisfiability algorithm for AC⁰.

Russell Impagliazzo, William Matthews, Ramamohan Paturi

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.

Paul Beame, Russell Impagliazzo, Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.

Paul Beame, Chris Beck, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2011

A Satisfiability Algorithm for AC$^0$

Russell Impagliazzo, William Matthews, Ramamohan Paturi

CoRR, 2011

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi

Comput. Complex., 2011

A Stronger Model of Dynamic Programming Algorithms.

Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo

Algorithmica, 2011

Relativized Separations of Worst-Case and Average-Case Complexities for NP.

Russell Impagliazzo

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

SIAM J. Comput., 2010

Constructive Proofs of Concentration Bounds.

Russell Impagliazzo, Valentine Kabanets

Electron. Colloquium Comput. Complex., 2010

Improved Algorithms for Unique Games via Divide and Conquer.

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

Electron. Colloquium Comput. Complex., 2010

Random Cnf's are Hard for the Polynomial Calculus.

Eli Ben-Sasson, Russell Impagliazzo

Comput. Complex., 2010

Communication Complexity with Synchronized Clocks.

Russell Impagliazzo, Ryan Williams

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

SIAM J. Comput., 2009

Chernoff-Type Direct Product Theorems.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

J. Cryptol., 2009

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

Russell Impagliazzo, Philippe Moser

Inf. Comput., 2009

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

Electron. Colloquium Comput. Complex., 2009

Security Amplification for InteractiveCryptographic Primitives.

Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

An axiomatic approach to algebrization.

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The Complexity of Satisfiability of Small Depth Circuits.

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

2008

The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.

Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi

J. Comput. Syst. Sci., 2008

On the Complexity of Succinct Zero-Sum Games.

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans

Comput. Complex., 2008

2007

The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.

Paul Beame, Russell Impagliazzo, Ashish Sabharwal

Comput. Complex., 2007

2006

Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.

Russell Impagliazzo, Nathan Segerlind

ACM Trans. Comput. Log., 2006

Extracting Randomness Using Few Independent Sources.

Boaz Barak, Russell Impagliazzo, Avi Wigderson

SIAM J. Comput., 2006

Logics for reasoning about cryptographic constructions.

Russell Impagliazzo, Bruce M. Kapron

J. Comput. Syst. Sci., 2006

Infinitely-Often Universal Languages and Diagonalization.

Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel

Electron. Colloquium Comput. Complex., 2006

Formula Caching in DPLL.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2006

Reducing The Seed Length In The Nisan-Wigderson Generator.

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Comb., 2006

Can every randomized algorithm be derandomized?

Russell Impagliazzo

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

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.

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Online Algorithms to Minimize Resource Reallocations and Network Communication.

Sashka Davis, Jeff Edmonds, Russell Impagliazzo

Proceedings of the Approximation, 2006

2005

Models of Greedy Algorithms for Graph Problems

Sashka Davis, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2005

Computational Complexity Since 1980.

Russell Impagliazzo

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.

Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo

SIAM J. Comput., 2004

Near Optimal Separation Of Tree-Like And General Resolution.

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Comb., 2004

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.

Valentine Kabanets, Russell Impagliazzo

Comput. Complex., 2004

2003

Hardness as randomness: a survey of universal derandomization

Russell Impagliazzo

CoRR, 2003

Anonymous credentials with biometrically-enforced non-transferability.

Russell Impagliazzo, Sara Miner More

Proceedings of the 2003 ACM Workshop on Privacy in the Electronic Society, 2003

Universal Languages and the Power of Diagonalization.

Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

A zero one law for RP.

Russell Impagliazzo, Philippe Moser

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Memoization and DPLL: Formula Caching Proof Systems.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

A Note on Conservativity Relations among Bounded Arithmetic Theories.

Russell Impagliazzo, Jan Krajícek

Math. Log. Q., 2002

In search of an easy witness: exponential time vs. probabilistic polynomial time.

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

J. Comput. Syst. Sci., 2002

Homogenization and the polynomial calculus.

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi

Comput. Complex., 2002

Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations.

Russell Impagliazzo, Nathan Segerlind

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

Randomness vs Time: Derandomization under a Uniform Assumption.

Russell Impagliazzo, Avi Wigderson

J. Comput. Syst. Sci., 2001

Which Problems Have Strongly Exponential Complexity?

Russell Impagliazzo, Ramamohan Paturi, Francis Zane

J. Comput. Syst. Sci., 2001

On the Complexity of k-SAT.

Russell Impagliazzo, Ramamohan Paturi

J. Comput. Syst. Sci., 2001

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi

J. Comput. Syst. Sci., 2001

On the (Im)possibility of Obfuscating Programs

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang

Electron. Colloquium Comput. Complex., 2001

Communication complexity towards lower bounds on circuit depth.

Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jirí Sgall

Comput. Complex., 2001

Reducing the complexity of reductions.

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

Comput. Complex., 2001

Hill-climbing finds random planted bisections.

Ted Carson, Russell Impagliazzo

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems.

Russell Impagliazzo

Proceedings of the Approximation, 2001

Counting Axioms Do Not Polynomially Simulate Counting Gates.

Russell Impagliazzo, Nathan Segerlind

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Resolution Complexity of Independent Sets in Random Graphs.

Paul Beame, Russell Impagliazzo, Ashish Sabharwal

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Extractors and pseudo-random generators with optimal seed length

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Electron. Colloquium Comput. Complex., 2000

Near-Optimal Separation of Treelike and General Resolution

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Electron. Colloquium Comput. Complex., 2000

A lower bound for DLL algorithms for <i>k</i>-SAT (preliminary version).

Pavel Pudlák, Russell Impagliazzo

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Homogenization and the Polynominal Calculus.

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

A Pseudorandom Generator from any One-way Function.

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby

SIAM J. Comput., 1999

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

Mihir Bellare, Russell Impagliazzo

IACR Cryptol. ePrint Arch., 1999

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.

Russell Impagliazzo, Pavel Pudlák, Jirí Sgall

Comput. Complex., 1999

Security-Preserving Hardness-Amplification for Any Regular One-Way Function.

Giovanni Di Crescenzo, Russell Impagliazzo

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

How to Forget a Secret.

Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson

Proceedings of the STACS 99, 1999

Near-Optimal Conversion of Hardness into Pseudo-Randomness.

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

The Relative Complexity of NP Search Problems.

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi

J. Comput. Syst. Sci., 1998

Improved Depth Lower Bounds for Small Distance Connectivity.

Paul Beame, Russell Impagliazzo, Toniann Pitassi

Comput. Complex., 1998

Go with the Winners for Graph Bisection.

Tassos Dimitriou, Russell Impagliazzo

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Randomness vs. Time: De-Randomization under a Uniform Assumption.

Russell Impagliazzo, Avi Wigderson

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Proofs of Membership vs. Proofs of Knowledge.

Giovanni Di Crescenzo, Russell Impagliazzo

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Bounding the Size of Planar Intertwines.

Arvind Gupta, Russell Impagliazzo

SIAM J. Discret. Math., 1997

Size-Depth Tradeoffs for Threshold Circuits.

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks

SIAM J. Comput., 1997

A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory.

Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami

Inf. Comput., 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

Russell Impagliazzo, Pavel Pudlák, Jirí Sgall

Electron. Colloquium Comput. Complex., 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.

Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall

Comput. Complex., 1997

<i>P = BPP</i> if <i>E</i> Requires Exponential Circuits: Derandomizing the XOR Lemma.

Russell Impagliazzo, Avi Wigderson

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Using Hard Problems to Derandomize Algorithms: An Incomplete Survey.

Russell Impagliazzo

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Does Parallel Repetition Lower the Error in Computationally Sound Protocols?

Mihir Bellare, Russell Impagliazzo, Moni Naor

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Efficient Cryptographic Schemes Provably as Secure as Subset Sum.

Russell Impagliazzo, Moni Naor

J. Cryptol., 1996

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution.

Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski

J. Comput. Syst. Sci., 1996

Towards an Analysis of Local Optimization Algorithms.

Tassos Dimitriou, Russell Impagliazzo

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability.

Matthew Clegg, Jeff Edmonds, Russell Impagliazzo

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Designated Verifier Proofs and Their Applications.

Markus Jakobsson, Kazue Sako, Russell Impagliazzo

Proceedings of the Advances in Cryptology, 1996

1995

The Reachability Problem for Finite Cellular Automata.

Andrea Clementi, Russell Impagliazzo

Inf. Process. Lett., 1995

Hard-Core Distributions for Somewhat Hard Problems.

Russell Impagliazzo

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Improved Depth Lower Vounds for Small Distance Connectivity.

Paul Beame, Russell Impagliazzo, Toniann Pitassi

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

A Personal View of Average-Case Complexity.

Russell Impagliazzo

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Pseudorandomness for network algorithms.

Russell Impagliazzo, Noam Nisan, Avi Wigderson

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Upper and Lower Bounds for Tree-Like Cutting Planes Proofs

Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart

Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

A Direct Product Theorem.

Russell Impagliazzo, Ran Raz, Avi Wigderson

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.

Andrea Clementi, Russell Impagliazzo

Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993

On Dice and Coins: Models of Computation for Random Generation

David Feldman, Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, Adi Shamir

Inf. Comput., June, 1993

The Effect of Random Restrictions on Formula Size.

Russell Impagliazzo, Noam Nisan

Random Struct. Algorithms, 1993

Exponential Lower Bounds for the Pigeonhole Principle.

Toniann Pitassi, Paul Beame, Russell Impagliazzo

Comput. Complex., 1993

Size-depth trade-offs for threshold circuits.

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

Computing Planar Intertwines

Arvind Gupta, Russell Impagliazzo

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

Russell Impagliazzo, Leonid A. Levin

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Security Preserving Amplification of Hardness

Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Limits on the Provable Consequences of One-Way Permutations

Russell Impagliazzo, Steven Rudich

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Pseudo-random Generation from one-way functions (Extended Abstracts)

Russell Impagliazzo, Leonid A. Levin, Michael Luby

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

How to Recycle Random Bits

Russell Impagliazzo, David Zuckerman

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

Russell Impagliazzo, Gábor Tardos

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)

Russell Impagliazzo, Michael Luby

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.

Russell Impagliazzo, Moni Naor

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Generic Oracles and Oracle Classes (Extended Abstract)

Manuel Blum, Russell Impagliazzo

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Direct Minimum-Knowledge Computations.

Russell Impagliazzo, Moti Yung

Proceedings of the Advances in Cryptology, 1987