## 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.