Search filters

List of works by Russell Impagliazzo

A Personal View of Average-Case Complexity

1995 scientific article by Russell Impagliazzo

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

scientific article (publication date: December 2004)

Exponential lower bounds for the pigeonhole principle

article published in 1993

Lower bounds on Hilbert’s Nullstellensatz and propositional proofs

On the Complexity of k-SAT

P = BPP if E requires exponential circuits

Reducing the complexity of reductions

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

Which Problems Have Strongly Exponential Complexity?

Paulina is supported by:

About Paulina

Help