Parity

Definition

TODO: extend the page to include parity of some specific $k$ bits out of the entire $n$.

The $n$-variable parity function is the Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ defined by $f(x)=x_1 \cdot x_2 \cdot \ldots \cdot x_n$. In other words, $f(x)=1$ if and only if the number of ones in the vector $x\in\{-1,1\}^n$ is odd.

Properties

• Parity only depends on the number of ones and is therefore a symmetric Boolean function.
• Over $\{-1,1\}$, the representation of the parity function is exactly the monomial $x_1 x_2 \ldots x_n$. Thus all of its Fourier mass rests on the highest level.
• The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 n − 1 monomials of length n and all conjunctive normal forms have the maximal number of 2 n − 1 clauses of length n. [1]
• Parity is not in AC0: A constant-depth Boolean circuit must have super-polynomial size in order to represent the parity function. [2] In fact, a circuit of depth $d$ must have size $\exp n^{\Theta (\frac{1}{d-1})}$ in order to exactly compute parity. This is tight: there exists a circuit of this size which computes parity. [3] [4]
• Parity cannot even be approximated in AC0: A circuit of depth $d$ and size $S$ can only have a correlation of $2^{-c_d n / (\log S)^{d-1} }$ with parity. [5]
• Parity over $n$ bits is odd when $n$ is odd, and even when $n$ is even.

References

1. Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, Template:Isbn, p. 260
2. Furst, Saxe, and Sipser Parity, Circuits, and the Polynomial-Time Hierarchy, 1984.
3. J. Håstad, Almost optimal lower bounds for small depth circuits, in Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC ’86, New York, ACM, 1986, pp. 6–20.
4. A. C-C. Yao, Separating the polynomial-time hierarchy by oracles , in Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’85, 1985, pp. 1–10
5. J. Håstad, On the Correlation of Parity and Small-Depth Circuits, SIAM J. Comput., 43(5), 1699–1708.