$$

• Circuit complexity landscape
• Gold standard pseudorandom generator

Constant depth: ${\mathsf{AC}}^0$

• switching lemmas
  • furst-saxe-sipser.pdf
  • Switching lemma
  • p-biased switching lemma
  • Small restrictions switching lemma
  • Multi-switching lemma
• DNF spectral theorem
• PRGs for AC0
• Approximating majority with constant depth
• Random projection basics
• Bottom-up and top-down LBs
• Karchmer–Wigderson game
• Bit unpredictability

Log depth: ${\mathsf{NC}}^1$

• barringtons-theorem.pdf
• Valiant’s depth reduction
• Matrix rigidity basics

General circuits: $\mathsf{P}/\mathrm{poly}$

• Almost all functions are complex
• Gate elimination
• Graph complexity

Branching programs

• Monotone non-deterministic BPs
• William Hoza - weighted PRGs
• nechiporuk.pdf