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

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 …

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 …

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 …

Any proof of P≠ NP will have to overcome two barriers: relativization and natural proofs. Yet
over the last decade, we have seen circuit lower bounds (eg, that PP does not have linear …

The P vs NP problem arose from the question of whether exhaustive search is necessary for
problems with short verifiable solutions. We still do not know if even a slight algorithmic …

A long-standing open question in computational learning theory is to prove NP-hardness of
learning efficient programs, the setting of which is in between proper learning and improper …

Restricting the search space {0, 1} n to the set of truth tables of “easy” Boolean functions on
log n variables, as well as using some known hardness–randomness tradeoffs, we establish …

Abstract In 1950, John Nash sent a remarkable letter to the National Security Agency, in
which—seeking to build theoretical foundations for cryptography—he all but formulated what …

This revised and extensively expanded edition of Computability and Complexity Theory
comprises essential materials that are core knowledge in the theory of computation. The …