Rolling parity

Definition

Let [math]n=k+2^{k}[/math]. The Rolling parity function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is defined as follows. The first [math]k[/math] bits are parsed as the binary representation of an integer [math]j\in\left[1,2^{k}\right][/math]. The value of [math]f[/math] is then the parity of the first [math]j[/math] bits:

[math] f(j, x) = \prod_{i=1}^j x_i[/math]

Properties

• The Fourier weight at level [math]i[/math] is at least a [math]1/k^2[/math] fraction of the total mass. It can be represented as a depth-3 circuit with AND, OR, NOT, XOR gates. It thus shows that it is possible for such a small-depth circuit to have weight distributed across the entire spectrum. See this stackexchange post.