## CS277: CONCRETE COMPLEXITY

Lecturer: Uri Zwick

Time: Tuesday, Thursday 2-3:30pm

Place: SODA 310

Lectures 1-2
- Basic concepts
- A characterization of complete bases (Post's theorem)
- An O(2^n/n) upper bound for all Boolean functions
- An Omega(2^n/n) lower bound for almost all Boolean functions
(Shannon's counting argument)

Lectures 3-4
- Boolean circuits vs. Turing machines
- The complexity of arithmetical operations (Addition and
Multiplication)

Lectures 5-6
- The complexity of arithmetical operations (Division in O(log n)
depth)
- Linear lower bounds

Lectures 7-8
- Formulae
- Formula size and circuit depth
- The lower bound of Neciporuk
- The lower bound of Khrapchenko

Lectures 9-10
- Rychkov's proof of Khrapchenko's bound
- Shrinkage of de Morgan formulae under restrictions
- The lower bound of Andreev

Lectures 11-12
- Polynomial size monotone formulae for majority
- Valiant's construction
- Non-deterministic and probabilistic circuits

Lectures 15-16
- The method of approximations
- A lower bound on the monotone size of 'is there a triangle?'
- A lower bound for larger cliques

Lectures 17-18
- A lower bound for larger cliques (continued).
- Communication complexity
- The correspondence between communication complexity and circuit depth

Lectures 19-20
- The log rank lower bound
- Randomized communication complexity
- Lower bound on the monotone depth of matching

Lectures 21-22
- Solution to some exercises
- Constant depth unboundad fanin circuits
- Lower bound for PARITY based on Hastad's switching lemma

Lectures 23-24
- Lower bound for PARITY using modulo 3 polynomials
- Halvers and epsilon-halvers

TAKE HOME EXAM

## OTHER CLASS NOTES ON CIRCUIT COMPLEXITY