4. DNF formulas and small-depth circuits🔗

DNF and CNF complexity, tribes and KKL, random restrictions, Håstad's Switching Lemma and the spectrum of DNFs, and the Linial–Mansour–Nisan theorem for constant-depth circuits.

1. 4.1. DNF formulas
2. 4.2. Tribes
3. 4.3. Random restrictions
4. 4.4. Håstad's Switching Lemma and the spectrum of DNFs
5. 4.5. Highlight: LMN's work on constant-depth circuits