Håstad switching lemma
= Håstad switching lemma
{c}
{wiki}
The Håstad switching lemma says that a small-width DNF or CNF becomes representable by a shallow <decision tree> with high probability under a sufficiently sparse random restriction. Iterating it is a central method for proving lower bounds against constant-depth circuits.