Lesson plan

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. 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.

Back to article

Article summary

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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.