HOME

TheInfoList



OR:

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, 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 Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation ...
to prove that AC0 Boolean circuits of depth ''k'' require size \exp(\Omega(n^)) to compute the
parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for it ...
on n bits. He was later awarded the
Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...
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 In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. In au ...
(that is, an AND of ORs) becomes a formula in
disjunctive normal form In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or in philosophical logic a ''cluster c ...
(an OR of ANDs) under random restriction, and vice versa. This "switching" gives the lemma its name.


Statement

Consider a width-w formula in
disjunctive normal form In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or in philosophical logic a ''cluster c ...
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(F \mid R_p) \geq t< C(pw)^t, where \operatorname(f) denotes decision tree complexity, the number of bits of x needed to compute the function f.


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 involves an argument with conditional probabilities. Arguably simpler proofs have been subsequently given by and . For an introduction, see Chapter 14 in .


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 James may refer to: People * James (given name) * James (surname) * James (musician), aka Faruq Mahfuz Anam James, (born 1964), Bollywood musician * James, brother of Jesus * King James (disambiguation), various kings named James * Prince Ja ...
and
Michael Sipser Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massa ...
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, and independently
Miklós Ajtai Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (devel ...
. 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. The switching lemma is the basis for bounds on the Fourier spectrum of AC0 circuits and algorithms for learning such circuits.


See also

* AC0 *
Boolean circuit In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
* Circuit satisfiability * Circuit value problem *
Parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for it ...


References

* * * * {{refend Computational complexity theory Circuit complexity