Andreev's function

Definition

Andreev's function is a variant of the address function. Let [math]r[/math] be a power of 2, let [math]n = 2^r[/math], and let [math]m = n/r[/math]. Andreev's function is a function [math]f:\{-1,1\}^n \times \{-1,1\}^n \to \{-1,1\}[/math], with [math]f(x,y)[/math] computed as follows:

• Arrange the first variable [math]x[/math] into an [math]r \times m[/math] matrix.
• For each row [math]i[/math], let [math]z_i = \mathrm{Parity}(x_{i1}, \ldots, x_{im})[/math]. This gives [math]r[/math] bits.
• Treat the bits [math](z_i)_{i=1}^{r}[/math] as a binary integer [math]j[/math], and output [math]y_j[/math].

Properties

• TODO. There is a result concerning AC0 circuits. See the book Boolean Function Complexity: advances and frontiers, chapter 6 (non-monotone formulas). See also works by Chen Santhanam and Srinivasan (16) or Kane and Williams (16).