## A taste of Circuit Complexity Pivoted at NEXP not in ACC0 (and more)

by Gil Cohen

#### Oded's comments

I just wish to call your attention to these lecture notes.
They summarize lectures given by Gil, covering basic material in
circuit complexity to the point of allowing to present Ryan's proof,
which is indeed the pivote and culmination of these lectures.

#### The original preface

A couple of years ago, Ryan Williams settled a long standing open problem
by showing that NEXP is not contained in ACC0.
To obtain this result, Williams applied an abundant of
classical as well as more recent results from complexity theory.
In particular, beautiful results concerning the tradeoffs between
hardness and randomness were used.
Some of the required building blocks for the proof, such as IP = PSPACE,
Toda's Theorem and the Nisan-Wigderson pseduorandom generator,
are well-documented in standard books on complexity theory, but others
such as the beautiful Impagliazzo-Kabanets-Wigderson Theorem, are not.

In this course we present Williams' proof assuming a fairly standard
knowledge in complexity theory. More precisely,
only an undergraduate-level background in complexity
(namely, Turing machines, "standard" complexity classes, reductions
and completeness) is assumed, but we also build upon several well-known
and well-documented results such as the above in a black-box fashion.
On the other hand, we allow ourselves to stray and discuss related topics,
not used in Williams' proof. In particular,
we cannot help but spending the last two lectures on matrix rigidity, which
is related to a classical wide-open problem in circuit complexity.

See copy posted on ECCC

Back to
list of Oded's choices.