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:

The class NC and its properties;

Charecterization of class P by circuits

The classes DLOG, NLOG, LogCFL and their properties

The class SC, proof of the relationship RL is a subset of SC

The class NC1 and its charecteriztions

The class TC0 and its charecterizations

The class ACC and its charecterizations

The class AC0 and its charecterizations

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.