Back to Circuit Lower Bound
Back to notes

# Parity is not in $\AC{0}$

60%

## Overview

In 1984, Furst, Saxe, and Sipser showed that the parity function does not lie in $\AC{0}$. Later on in 1986, Hastad showed an substantial improvement in his Ph.D. thesis.

We are going to prove the following theorem in several ways and discuss the implication as well as influence of this theorem.

For sufficiently large $n$ and constant $d$, parity function on $n$-bits cannot be computed by depth $d$ size $2^{n^{o(1/d)}}$ circuits with unbounded fan-in AND, OR gates.

Parity is not in $\AC{0}$.

### Proof ideas

In this note, we present three different proofs

## Switching lemma

In 1986, Hastad proved the following switching lemma.

Suppose function $f:\bit^n\rightarrow\bit$ can be expressed by $k$-DNF, and let $\rho$ be a random restriction on $t$ selected bits. Then, for any $s\geq2$, $$\mathbb{P}_{\rho}[f\vert_{\rho} \text{ is not expressible as a } s-\text{CNF}]\leq(\frac{(n-t)k^{10}}{n})^{s/2}.$$

Now, we show how to use switching lemma to prove our main theorem.

### Step 1: Turn circuit into general position

Let’s fix arbitrary $AC{0}$ circuit $C$ and turn it into general position. Namely,

• The fan-out of every gates is 1 so that $C$ is a tree.
• All the NOT gates lie in first layer of $C$.
• The AND and OR gates are switching between layers.
• The input/bottom layer consists of OR gates with fan-in 1.

Note that we can turn every $AC{0}$ circuit into this form with at most polynomial blow up in size. As a result, we can assume $C$ is of size upper bounded by $n^b$ and of depth $d$.

### Step 2: Reduce depth by random restriction

In this step, we use switching lemma together with union bound and probabilistic method to reduce the depth of the circuit. Concretely, we want to inductively show the following: After the $i$th iteration for $i=1,\dots d-1$.

• The circuit has depth $d-i$.
• The gates in the bottom layer have fan-in at most $k_i$ where $k_i$ is a constant set later.
• The gates in the layer above the bottom layer can be expressed with a
• There are $n_i-\sqrt{n_i}$ inputs being fixed and $\sqrt{n_i}$ left undetermined where $n_0=n$ and $n_i=n^{1/2^{i}}$.

We achieve the above setting by the following probabilistic argument.

1. By induction, we know that at the beginning of the $i$th iteration, the gates in the layer above the bottom layer can be expressed as a $(k_{i-1})$-CNF (or $(k_{i-1})$-DNF). Thus, we can apply Hastad’s switching lemma.
2. For a single gate in the layer above the bottom layer, the probability of cannot be expressed as a $k_i$-DNF (or $k_i$-CNF) is at most $$(\frac{\sqrt{n_i}k_{i-1}^{10}}{n_i})^{k_i/2}.$$

Take $k_i=10b2^{i+2}$, the probability is upper bounded by $1/(10n^{n^b})$. As a result, by union bound and probabilistic argument, we know that there exists a restriction of size $n_i-\sqrt{n_i}$ such that every gates in the layer above the bottom layer can be expressed as a $k_i$-DNF (or $k_i$-DNF). As a result, we can combine the layer above the bottom layer with the layer above into a single layer.

### Step 3: Final step

After $d-2$ iteration, the circuit has the following properties.

• Having $n_{d-2}=n^{1/2^{d-2}}$ input bits remain unfixed.
• The circuit can be expressed as a $k_{d-2}$-CNF (or $k_{d-2}$-DNF).

As a result, the output of the circuit can be determined by $k_{d-2}$ value which is a constant with respect to the remaining unfixed input bits. As the parity function cannot be determined until the last bit is fixed, we know that $C$ cannot compute the parity function.