# Andreev's function

## Definition

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

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

## Properties

• Andreev's function cannot be computed or approximated by depth-2 linear threshold circuits with a linear amount of gates: Any function which agrees with Andreev's function on at least $1/2 + \varepsilon$ fraction of the inputs requires at least $\Omega(\varepsilon^3 n^{3/2} / \log ^3 (n))$ gates (for large enough $\varepsilon$). [1]
• TODO. There are more results in this vein. See the book Boolean Function Complexity: advances and frontiers, chapter 6 (non-monotone formulas). See also work by Chen Santhanam and Srinivasan (16) and add the results.