The Switching Lemma

Hastad's Switching Lemma is one of the gems of computational complexity. The switching lemma analyzes the effect of random restrictions on $latex AC^0$ circuits, which are constant depth circuits with AND, OR and NOT gates of unbounded fanin. It says that such restrictions tends to simplify  $latex AC^0$ circuits in surprising ways. An immediate consequence of the switching lemma is strong … Continue reading The Switching Lemma