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.