CS 642: Circuit Complexity Theory
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.