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.
To be announced by the instructor.