CS277: CONCRETE COMPLEXITY

• 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)

• Boolean circuits vs. Turing machines
• The complexity of arithmetical operations (Addition and Multiplication)

• The complexity of arithmetical operations (Division in O(log n) depth)
• Linear lower bounds

• Formulae
• Formula size and circuit depth
• The lower bound of Neciporuk
• The lower bound of Khrapchenko

• Rychkov's proof of Khrapchenko's bound
• Shrinkage of de Morgan formulae under restrictions
• The lower bound of Andreev

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

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

• A lower bound for larger cliques (continued).
• Communication complexity
• The correspondence between communication complexity and circuit depth

• The log rank lower bound
• Randomized communication complexity
• Lower bound on the monotone depth of matching

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

• Lower bound for PARITY using modulo 3 polynomials
• Halvers and epsilon-halvers

OTHER CLASS NOTES ON CIRCUIT COMPLEXITY

• Lectures on the Fusion Method and Derandomization (lectures by Avi Wigderson)
• Complexity Theory Lecture Notes (lectures by Eric Allender)