CS 642: Circuit Complexity Theory

Course Contents:

The course aims at a comprehensive overview of results on the circuit complexity classes and their relationship with the Turing based classes. The topics to be covered in the course are as follows:

1. The class NC and its properties;
2. Charecterization of class P by circuits
3. The classes DLOG, NLOG, LogCFL and their properties
4. The class SC, proof of the relationship RL is a subset of SC
5. The class NC1 and its charecteriztions
6. The class TC0 and its charecterizations
7. The class ACC and its charecterizations
8. The class AC0 and its charecterizations
9. Lower bounds for AC0, for AC0[m] where_m_is a prime power and for TC02.

Books and References:

To be announced by the instructor.