Difference between revisions of "Andreev's function"
(Mainly a stub for now.) |
m |
||
| Line 6: | Line 6: | ||
== Properties == | == Properties == | ||
| − | * TODO. There | + | * 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>). <ref>Daniel M. Kane, Ryan Williams, [https://arxiv.org/pdf/1511.07860.pdf Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits]</ref> |
| + | * 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 == | == References == | ||
Revision as of 06:01, 1 October 2018
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
