Andreev's function
Contents
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
- 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 [math]1/2 + \varepsilon[/math] fraction of the inputs requires at least [math]\Omega(\varepsilon^3 n^{3/2} / \log ^3 (n))[/math] gates (for large enough [math]\varepsilon[/math]). [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.
References
- ↑ Daniel M. Kane, Ryan Williams, Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
