Boolean Function Complexity, Autumn 2022
A basic approach to P v.s. NP problem is through circuit complexity. Circuits provide a basic model for computing Boolean functions. We will show that several explicit functions cannot be computed by small circuits from various interesting restricted classes.
Instructor
Lectures
- Oct 7: Introduction to circuits, Shannon's bound, gate elimination.
- Oct 14: Gate elimination cont'd, Lupanov's upper bound.
- Oct 21: Communication complexity, Karchmer-Wigderson games.
- Nov 4: KRW conjecture, multiplexor lower bound, see [EIRS] and [Meir].
- Nov 11: Multiplexor lower bound cont'd, VC-dimension, Sauer-Shelah lemma.
- Nov 18: Shrinkage of De Morgan formulas, lower bounds for Parity and Andreev's function
- Nov 25: Khrapchenko's bound, Nechiporuk's bound and Element Distinctness.
- Dec 2: Introduction to Switching Lemma, see [Beame] and [Thapen].
- Dec 16: Applying SL, lower bound for parity, decision tree upper bound and k-SAT
Literature
- [J] Jukna, Boolean Function Complexity, Springer.
When and where
Karlín K3, Fridays at 15:40.