# Parity

## Definition

**TODO**: extend the page to include parity of some specific [math]k[/math] bits out of the entire [math]n[/math].

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

## Properties

- Parity only depends on the number of ones and is therefore a symmetric Boolean function.
- Over [math]\{-1,1\}[/math], the representation of the parity function is exactly the monomial [math]x_1 x_2 \ldots x_n[/math]. 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 AC
^{0}: A constant-depth Boolean circuit must have super-polynomial size in order to represent the parity function.^{[2]}In fact, a circuit of depth [math]d[/math] must have size [math]\exp n^{\Theta (\frac{1}{d-1})}[/math] 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 AC
^{0}: A circuit of depth [math]d[/math] and size [math]S[/math] can only have a correlation of [math]2^{-c_d n / (\log S)^{d-1} }[/math] with parity.^{[5]}

- Parity cannot even be approximated in AC
- Parity over [math]n[/math] bits is odd when [math]n[/math] is odd, and even when [math]n[/math] is even.

## References

- ↑ Ingo Wegener, Randall J. Pruim,
*Complexity Theory*, 2005, Template:Isbn, p. 260 - ↑ Furst, Saxe, and Sipser Parity, Circuits, and the Polynomial-Time Hierarchy, 1984.
- ↑ 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.
- ↑ 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
- ↑ J. Håstad, On the Correlation of Parity and Small-Depth Circuits, SIAM J. Comput., 43(5), 1699–1708.