Lecture Notes:

• Lecture 1. De Morgan Circuits, Formulas, Uniformity, Riordan-Shannon's lower bounds.


• Lecture 2. Lupanov's upper bound, Gate elimination technique, Linear lower bounds against circuits.


• Lecture 3. Formula depth reduction, Khrapchenko's lower bound, Subbotovskaya's method of random restrictions.


• Lecture 4. Subbotovskaya's method (contd.), Shrinkage of formulas, Andreev's function, Neciporuk's method.


• Lecture 5. Decision tree complexity, Certificate complexity, P = NP ∩ coNP for decision tree depth, Sensitivity.


• Lecture 6. Block sensitivity, polynomial representation, degree.


• Lecture 7. Introduction to Fourier analysis, Lower bound for decision tree size.


• Lecture 8. Razborov - Smolensky's lower bound for constant depth circuits.


• Lecture 9. Hastad's Switching Lemma.


• Lecture 10. Switching Lemma continued, Lower bound for Parity, Intro to LMN theorem.


• Lecture 11. LMN Theorem and constant depth circuits.