Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2025

Lower bounds for the Bit Pigeonhole Principle in Bounded-Depth Resolution over Parities.

[BibT_eX]

[DOI]

Farzan Byramji

Electron. Colloquium Comput. Complex., 2025

The Computational Complexity of Factored Graphs.

[BibT_eX]

[DOI]

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Lifting to Randomized Parity Decision Trees.

[BibT_eX]

[DOI]

Farzan Byramji

Proceedings of the Approximation, 2025

2024

The Greedy Coin Change Problem.

[BibT_eX]

[DOI]

Shreya Gupta

Boyang Huang

CoRR, 2024

Replicability in High Dimensional Statistics.

[BibT_eX]

[DOI]

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

2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.

[BibT_eX]

[DOI]

Ilya Volkovich

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

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

TFNP Characterizations of Proof Systems and Monotone Circuits.

[BibT_eX]

[DOI]

Sam Buss

Noah Fleming

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields.

[BibT_eX]

[DOI]

Sasank Mouli

Proceedings of the 38th Computational Complexity Conference, 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.

[BibT_eX]

[DOI]

Ilya Volkovich

Proceedings of the Approximation, 2023

2022

Reproducibility in learning.

[BibT_eX]

[DOI]

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

2021

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

[BibT_eX]

[DOI]

Maria Paula Parga Nina

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?).

[BibT_eX]

[DOI]

Sam McGuire

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Lifting for Constant-Depth Circuits and Applications to MCSP.

[BibT_eX]

[DOI]

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

Boosting in the Presence of Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

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

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

On the Power and Limitations of Branch and Cut.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

The Surprising Power of Constant Depth Algebraic Proofs.

[BibT_eX]

[DOI]

Sasank Mouli

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

2019

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

Jiawei Gao

Electron. Colloquium Comput. Complex., 2019

UTIME Easy-witness Lemma & Some Consequences.

[BibT_eX]

[DOI]

Anant Dhayal

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

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

2018

Half-Duplex Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Stabbing Planes.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

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

[BibT_eX]

[DOI]

Marco L. Carmosino

Manuel Sabin

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

The Power of Natural Properties as Oracles.

[BibT_eX]

[DOI]

Ilya Volkovich

Proceedings of the 33rd Computational Complexity Conference, 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Does Looking Inside a Circuit Help?.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Agnostic Learning from Tolerant Natural Proofs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

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

[BibT_eX]

[DOI]

Chris Beck

SIAM J. Comput., 2016

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

[BibT_eX]

[DOI]

Jiawei Gao

Electron. Colloquium Comput. Complex., 2016

Algorithms from Natural Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Learning Algorithms from Natural Proofs.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

Pseudorandomness When the Odds are Against You.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Tighter Connections between Derandomization and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

An Entropic Proof of Chang's Inequality.

[BibT_eX]

[DOI]

Cristopher Moore

Alexander Russell

SIAM J. Discret. Math., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Fourier Concentration from Shrinkage.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

AM with Multiple Merlins.

[BibT_eX]

[DOI]

Scott Aaronson

Dana Moshkovitz

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Strong ETH holds for regular resolution.

[BibT_eX]

[DOI]

Christopher Beck

Proceedings of the Symposium on Theory of Computing Conference, 2013

Exact Complexity and Satisfiability - (Invited Talk).

[BibT_eX]

[DOI]

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

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.

[BibT_eX]

[DOI]

Stefan Schneider

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

Finding Heavy Hitters from Lossy or Noisy Data.

[BibT_eX]

[DOI]

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

2012

A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits

[BibT_eX]

[DOI]

Stefan Schneider

CoRR, 2012

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space.

[BibT_eX]

[DOI]

Christopher Beck

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A satisfiability algorithm for AC0.

[BibT_eX]

[DOI]

William Matthews

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Pseudorandomness from Shrinkage.

[BibT_eX]

[DOI]

Raghu Meka

David Zuckerman

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

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

[BibT_eX]

[DOI]

Chris Beck

Shachar Lovett

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

A Satisfiability Algorithm for AC$^0$

[BibT_eX]

[DOI]

William Matthews

CoRR, 2011

A Stronger Model of Dynamic Programming Algorithms.

[BibT_eX]

[DOI]

Joshua Buresh-Oppenheim

Sashka Davis

Algorithmica, 2011

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

[BibT_eX]

[DOI]

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

2010

Improved Algorithms for Unique Games via Divide and Conquer.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

On the Exact Complexity of Evaluating Quantified k-CNF.

[BibT_eX]

[DOI]

Chris Calabro

Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

Communication Complexity with Synchronized Clocks.

[BibT_eX]

[DOI]

Ryan Williams

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

Constructive Proofs of Concentration Bounds.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

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

[BibT_eX]

[DOI]

Ragesh Jaiswal

SIAM J. Comput., 2009

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

[BibT_eX]

[DOI]

Philippe Moser

Inf. Comput., 2009

Toward a Model for Backtracking and Dynamic Programming.

[BibT_eX]

[DOI]

Michael Alekhnovich

Allan Borodin

Joshua Buresh-Oppenheim

Avner Magen

Electron. Colloquium Comput. Complex., 2009

Security Amplification for InteractiveCryptographic Primitives.

[BibT_eX]

[DOI]

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

New direct-product testers and 2-query PCPs.

[BibT_eX]

[DOI]

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

The Complexity of Satisfiability of Small Depth Circuits.

[BibT_eX]

[DOI]

Chris Calabro

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

An Axiomatic Approach to Algebrization.

[BibT_eX]

[DOI]

Antonina Kolokolova

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

2008

Uniform direct product theorems: simplified, optimized, and derandomized.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

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

[BibT_eX]

[DOI]

Ashish Sabharwal

Comput. Complex., 2007

Chernoff-Type Direct Product Theorems.

[BibT_eX]

[DOI]

Ragesh Jaiswal

Proceedings of the Advances in Cryptology, 2007

2006

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2006

Infinitely-Often Universal Languages and Diagonalization.

[BibT_eX]

[DOI]

Alan Nash

Jeffrey B. Remmel

Electron. Colloquium Comput. Complex., 2006

Formula Caching in DPLL.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Reducing The Seed Length In The Nisan-Wigderson Generator.

[BibT_eX]

[DOI]

Ronen Shaltiel

Comb., 2006

Can every randomized algorithm be derandomized?

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Ragesh Jaiswal

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

A Duality between Clause Width and Clause Density for SAT.

[BibT_eX]

[DOI]

Chris Calabro

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

Online Algorithms to Minimize Resource Reallocations and Network Communication.

[BibT_eX]

[DOI]

Sashka Davis

Jeff Edmonds

Proceedings of the Approximation, 2006

2005

Computational Complexity Since 1980.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

On the Complexity of Succinct Zero-Sum Games.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Toward a Model for Backtracking and Dynamic Programming.

[BibT_eX]

[DOI]

Michael Alekhnovich

Allan Borodin

Joshua Buresh-Oppenheim

Avner Magen

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Near Optimal Separation Of Tree-Like And General Resolution.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Comb., 2004

Models of greedy algorithms for graph problems.

[BibT_eX]

[DOI]

Sashka Davis

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Extracting Randomness Using Few Independent Sources.

[BibT_eX]

[DOI]

Boaz Barak

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Hardness as randomness: a survey of universal derandomization

[BibT_eX]

[DOI]

CoRR, 2003

Anonymous credentials with biometrically-enforced non-transferability.

[BibT_eX]

[DOI]

Sara Miner More

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

Derandomizing polynomial identity tests means proving circuit lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Logics for Reasoning about Cryptographic Constructions.

[BibT_eX]

[DOI]

Bruce M. Kapron

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

Universal Languages and the Power of Diagonalization.

[BibT_eX]

[DOI]

Alan Nash

Jeffrey B. Remmel

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

A zero one law for RP.

[BibT_eX]

[DOI]

Philippe Moser

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

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

[BibT_eX]

[DOI]

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

Memoization and DPLL: Formula Caching Proof Systems.

[BibT_eX]

[DOI]

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

2002

A Note on Conservativity Relations among Bounded Arithmetic Theories.

[BibT_eX]

[DOI]

Jan Krajícek

Math. Log. Q., 2002

Homogenization and the polynomial calculus.

[BibT_eX]

[DOI]

Josh Buresh-Oppenheim

Matthew Clegg

Comput. Complex., 2002

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

[BibT_eX]

[DOI]

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

A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.

[BibT_eX]

[DOI]

Samuel R. Buss

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Randomness vs Time: Derandomization under a Uniform Assumption.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Hill-climbing finds random planted bisections.

[BibT_eX]

[DOI]

Ted Carson

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

Counting Axioms Do Not Polynomially Simulate Counting Gates.

[BibT_eX]

[DOI]

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

On the (Im)possibility of Obfuscating Programs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2001

In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.

[BibT_eX]

[DOI]

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

Resolution Complexity of Independent Sets in Random Graphs.

[BibT_eX]

[DOI]

Ashish Sabharwal

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

2000

Near-Optimal Separation of Treelike and General Resolution

[BibT_eX]

[DOI]

Eli Ben-Sasson

Electron. Colloquium Comput. Complex., 2000

Extractors and pseudo-random generators with optimal seed length.

[BibT_eX]

[DOI]

Ronen Shaltiel

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

A lower bound for DLL algorithms for k-SAT (preliminary version).

[BibT_eX]

[DOI]

Pavel Pudlák

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

Homogenization and the Polynominal Calculus.

[BibT_eX]

[DOI]

Josh Buresh-Oppenheim

Matthew Clegg

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

1999

A Pseudorandom Generator from any One-way Function.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

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

[BibT_eX]

[DOI]

Mihir Bellare

IACR Cryptol. ePrint Arch., 1999

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

[BibT_eX]

[DOI]

Pavel Pudlák

Jirí Sgall

Comput. Complex., 1999

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

[BibT_eX]

[DOI]

Giovanni Di Crescenzo

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

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

[BibT_eX]

[DOI]

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

How to Forget a Secret.

[BibT_eX]

[DOI]

Giovanni Di Crescenzo

Niels Ferguson

Markus Jakobsson

Proceedings of the STACS 99, 1999

Near-Optimal Conversion of Hardness into Pseudo-Randomness.

[BibT_eX]

[DOI]

Ronen Shaltiel

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

Random CNF's are Hard for the Polynomial Calculus.

[BibT_eX]

[DOI]

Eli Ben-Sasson

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

Complexity of k-SAT.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

1998

Improved Depth Lower Bounds for Small Distance Connectivity.

[BibT_eX]

[DOI]

Comput. Complex., 1998

Go with the Winners for Graph Bisection.

[BibT_eX]

[DOI]

Tassos Dimitriou

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

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

[BibT_eX]

[DOI]

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

Which Problems Have Strongly Exponential Complexity?

[BibT_eX]

[DOI]

Francis Zane

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

Proofs of Membership vs. Proofs of Knowledge.

[BibT_eX]

[DOI]

Giovanni Di Crescenzo

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

1997

Bounding the Size of Planar Intertwines.

[BibT_eX]

[DOI]

Arvind Gupta

SIAM J. Discret. Math., 1997

Size-Depth Tradeoffs for Threshold Circuits.

[BibT_eX]

[DOI]

Michael E. Saks

SIAM J. Comput., 1997

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

[BibT_eX]

[DOI]

Stephen A. Cook

Tomoyuki Yamakami

Inf. Comput., 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

[BibT_eX]

[DOI]

Pavel Pudlák

Jirí Sgall

Electron. Colloquium Comput. Complex., 1997

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

[BibT_eX]

[DOI]

Alexander A. Razborov

Jirí Sgall

Comput. Complex., 1997

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.

[BibT_eX]

[DOI]

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

Reducing the Complexity of Reductions.

[BibT_eX]

[DOI]

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

Using Hard Problems to Derandomize Algorithms: An Incomplete Survey.

[BibT_eX]

[DOI]

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

Does Parallel Repetition Lower the Error in Computationally Sound Protocols?

[BibT_eX]

[DOI]

Mihir Bellare

Moni Naor

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

1996

Towards an Analysis of Local Optimization Algorithms.

[BibT_eX]

[DOI]

Tassos Dimitriou

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

Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability.

[BibT_eX]

[DOI]

Matthew Clegg

Jeff Edmonds

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

Designated Verifier Proofs and Their Applications.

[BibT_eX]

[DOI]

Markus Jakobsson

Kazue Sako

Proceedings of the Advances in Cryptology, 1996

1995

The Reachability Problem for Finite Cellular Automata.

[BibT_eX]

[DOI]

Andrea Clementi

Inf. Process. Lett., 1995

The relative complexity of NP search problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Hard-Core Distributions for Somewhat Hard Problems.

[BibT_eX]

[DOI]

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

Improved Depth Lower Vounds for Small Distance Connectivity.

[BibT_eX]

[DOI]

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

A Personal View of Average-Case Complexity.

[BibT_eX]

[DOI]

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

1994

Pseudorandomness for network algorithms.

[BibT_eX]

[DOI]

Noam Nisan

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

Upper and Lower Bounds for Tree-Like Cutting Planes Proofs

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

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

A Direct Product Theorem.

[BibT_eX]

[DOI]

Ran Raz

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.

[BibT_eX]

[DOI]

Andrea Clementi

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

1993

The Effect of Random Restrictions on Formula Size.

[BibT_eX]

[DOI]

Noam Nisan

Random Struct. Algorithms, 1993

Exponential Lower Bounds for the Pigeonhole Principle.

[BibT_eX]

[DOI]

Comput. Complex., 1993

Size-depth trade-offs for threshold circuits.

[BibT_eX]

[DOI]

Michael E. Saks

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

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

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

1992

Exponential Lower Bounds for the Pigeonhole Principle

[BibT_eX]

[DOI]

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

1991

Computing Planar Intertwines

[BibT_eX]

[DOI]

Arvind Gupta

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

Communication Complexity Towards Lower Bounds on Circuit Depth

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Leonid A. Levin

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

Security Preserving Amplification of Hardness

[BibT_eX]

[DOI]

Oded Goldreich

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

[BibT_eX]

[DOI]

Steven Rudich

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

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

[BibT_eX]

[DOI]

Leonid A. Levin

Michael Luby

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

On Dice and Coins: Models of Computation for Random Generation.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

How to Recycle Random Bits

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Gábor Tardos

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

Efficient Cryptographic Schemes Provably as Secure as Subset Sum

[BibT_eX]

[DOI]

Moni Naor

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)

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Moni Naor

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

1987

Generic Oracles and Oracle Classes (Extended Abstract)

[BibT_eX]

[DOI]

Manuel Blum

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

Direct Minimum-Knowledge Computations.

[BibT_eX]

[DOI]