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

• Navid Talebanfard

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.