Andreev's function

From Boolean Zoo
Jump to: navigation, search


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].


  • 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.


See also