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 AC0 Boolean circuits of depth k require size exp⁡(Ω(n1/(k−1))) to compute the parity function on n bits.[1] 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.

## Contents

* 1 Statement
* 1.1 Proof
* 2 Bounds on AC0 circuits
* 3 See also
* 4 References

## Statement

Consider a width-w formula in disjunctive normal form (abbreviated as DNF) F=C1∨C2∨⋯∨Cm, the OR of clauses Cℓ which are the AND of w literals (xi or its negation ¬xi). For example, (¬x1∧x2)∨(x2∧x3)∨(x2∧x3) is an example of a formula in this form with width 2.

Let F|Rp denote the formula under a random restriction: each xi 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⁡[DT⁡(F∣Rp)≥t]<C(pw)t,

where DT⁡(f) denotes decision tree complexity, the number of bits of x needed to compute the function f.[2]

### Proof

Intuitively, the switching lemma holds because DNF formulas shrink significantly under random restriction: when a literal in a clause is set to 0, the whole AND clause evaluates to zero, and therefore can be discarded.

The original proof of the switching lemma (Håstad 1987) involves an argument with conditional probabilities. Arguably simpler proofs have been subsequently given by (Razborov 1993) and (Beame 1994). For an introduction, see Chapter 14 in (Arora Barak).

## Bounds on AC0 circuits

The switching lemma is a key tool used for understanding the circuit complexity class AC0, which consists of constant-depth circuits consisting of AND, OR, and NOT. Håstad's initial application of this lemma was to establish tight exponential lower bounds for such circuits computing PARITY, improving on the prior super-polynomial lower bounds of Merrick Furst, James Saxe and Michael Sipser[3] and independently Miklós Ajtai.[4] This is done by applying the switching lemma d−1 times, where d is the depth of the circuit: each application removes a layer of the circuit until one is left with a very simple circuit, whereas PARITY is still PARITY under random restriction, and so remains complex. So, a circuit that computes PARITY must have high depth.[5]

The switching lemma is the basis for bounds on the Fourier spectrum of AC0 circuits[5] and algorithms for learning such circuits.[6]

## See also

* AC0
* Boolean circuit
* Circuit satisfiability
* Circuit value problem
* Parity function

## References

1. ↑ Håstad, Johan (1986). "Almost optimal lower bounds for small depth circuits" (in en). Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. ACM Press. pp. 6–20. doi:10.1145/12130.12132. ISBN 978-0-89791-193-1. http://portal.acm.org/citation.cfm?doid=12130.12132.
2. ↑ Rossman, Benjamin (2019) (in en). Criticality of Regular Formulas. Leibniz International Proceedings in Informatics (LIPIcs). 137. Michael Wagner. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 1:1–1:28. doi:10.4230/LIPICS.CCC.2019.1. ISBN 978-3-95977-116-0. http://drops.dagstuhl.de/opus/volltexte/2019/10823/.
3. ↑ Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Computer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13-27, doi:10.1007/BF01744431
4. ↑ Miklós Ajtai, "Σ11-Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1-48.
5. ↑ 5.0 5.1 Tal, Avishay (2017) (in en). Tight Bounds on the Fourier Spectrum of AC0. Leibniz International Proceedings in Informatics (LIPIcs). 79. Marc Herbstritt. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 15:1–15:31. doi:10.4230/LIPICS.CCC.2017.15. ISBN 978-3-95977-040-8. http://drops.dagstuhl.de/opus/volltexte/2017/7525/.
6. ↑ Linial, Nathan; Mansour, Yishay; Nisan, Noam (1993-07-01). "Constant depth circuits, Fourier transform, and learnability". Journal of the ACM 40 (3): 607–620. doi:10.1145/174130.174138. ISSN 0004-5411.

* Computational Complexity: A Modern Approach, Cambridge, 2009, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/
* Beame, Paul (1994), "A Switching Lemma Primer", Manuscript
* Håstad, Johan (1987), Computational limitations of small depth circuits, Ph.D. thesis, Massachusetts Institute of Technology, http://www.nada.kth.se/~johanh/thesis.pdf.
* "An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic", Arithmetic, Proof Theory and Computational Complexity 23: 247–277, 1993, doi:10.1093/oso/9780198536901.003.0012, ISBN 978-0-19-853690-1

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Switching lemma. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Switching_lemma&oldid=3984048"