Switching lemma
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. It was first introduced by Johan Håstad to prove that AC 0 Boolean circuits of depth k require size \exp(\Omega(n^{1/(k-1)})) to compute the parity function on n bits. He was later awarded the Gödel Prize for this work in 1994.
The switching lemma describes the behavior of a depth-2 circuit under random restriction, i.e. when randomly fixing most of the coordinates to 0 or 1. Specifically, from the lemma, it follows that a formula in conjunctive normal form (that is, an AND of ORs) becomes a formula in disjunctive normal form (an OR of ANDs) under random restriction, and vice versa.
This "switching" gives the lemma its name. Consider a width- w formula in disjunctive normal form (abbreviated as DNF) F = C_1 \vee C_2 \vee \cdots \vee C_m , the OR of clauses C_\ell which are the AND of w literals ( x_i or its negation \neg x_i ). For example, (\neg x_1 \wedge x_2) \vee (x_2 \wedge x_3) \vee (x_2 \wedge x_3) is an example of a formula in this form with width 2.
Let F | R_p denote the formula under a random restriction: each x_i is set independently to 0 or 1 with probability (1-p)/2 . Then, for a sufficiently large constant C, the switching lemma states that \Pr[ \operatorname{DT}(F \mid R_p) \geq t] where \operatorname{DT}(f) denotes decision tree complexity, the number of bits of x needed to compute the function f .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360740106 under CC BY-SA 4.0; modifications have been made.