This book is rooted in the thesis that complexity theory is extremely rich in conceptual
content, and that this contents should be explicitly communicated in expositions and courses …

This beginning graduate textbook describes both recent achievements and classical results
of computational complexity theory. Requiring essentially no background apart from …

Pseudorandom generators are fundamental to many theoretical and applied aspects of
computing. We show how to construct a pseudorandom generator from any one-way …

This is a survey of pseudorandomness, the theory of efficiently generating objects that" look
random" despite being constructed using little or no randomness. This theory has …

This paper addresses the relationship between three central questions in complexity theory.
First, to what extent can a problem be easier to solve for probabilistic algorithms than for …

We show that derandomizing Polynomial Identity Testing is, essentially, equivalent to
proving circuit lower bounds for NEXP. More precisely, we prove that if one can test in …

Abstract For x, y∈ 0, 1*, the point function P x, y is defined by P x, y (x)= y and P x, y (x′)= 0|
y| for all x′≠ x. We introduce the notion of a distributed point function (DPF), which is a …

Abstract Impagliazzo and Wigderso”[lW97] have recently show” that if there exists a decision
problem solvable in time Z” cn) and having circuit complexity Z”(“)(for all but tinitely many n) …

We introduce a new approach to constructing extractors. Extractors are algorithms that
transform a “weakly random” distribution into an almost uniform distribution. Explicit …

The class ACC consists of circuit families with constant depth over unbounded fan-in AND,
OR, NOT, and MODm gates, where m> 1 is an arbitrary constant. We prove the following …