Documentation

Complexitylib.Algebraic.LowerBound.KarchmerWigderson

Karchmer–Wigderson games and the KRW conjecture #

This umbrella collects De Morgan formulas, Karchmer–Wigderson protocols, the theorem identifying formula depth and size with protocol depth and size (for n ≥ 1 input bits), the composition of Boolean functions with its elementary bounds, and the statement of the Karchmer–Raz–Wigderson conjecture.