Difference between revisions of "Inner product"
(→Properties) |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
A function <math>f:\{-1,1\}^{2k} \to \{-1,1\}</math> is called an '''inner product function''' if it is equal to the sign of the inner product of the first half of the input and the second half. More formally, | A function <math>f:\{-1,1\}^{2k} \to \{-1,1\}</math> is called an '''inner product function''' if it is equal to the sign of the inner product of the first half of the input and the second half. More formally, | ||
| − | <math>f(x_1,\ldots,x_k, y_1,\ldots,y_k) = (-1)^{\boldsymbol{x} \cdot \boldsymbol{y}}. </math> | + | :::{| class="wikitable" |
| − | + | |- | |
| + | |<math>f(x_1,\ldots,x_k, y_1,\ldots,y_k) = (-1)^{\boldsymbol{x} \cdot \boldsymbol{y}}. </math> | ||
| + | |} | ||
== Properties == | == Properties == | ||
* TODO: Fourier representation | * TODO: Fourier representation | ||
* The inner product function requires either exponential weights or an exponential number of nodes to be represented with a restricted Boltzmann machine. <ref>Theorem 9 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, [https://www.cs.toronto.edu/~toni/Papers/nips2013.pdf On the Representational Efficiency of Restricted Boltzmann Machines], NIPS 2013</ref> | * The inner product function requires either exponential weights or an exponential number of nodes to be represented with a restricted Boltzmann machine. <ref>Theorem 9 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, [https://www.cs.toronto.edu/~toni/Papers/nips2013.pdf On the Representational Efficiency of Restricted Boltzmann Machines], NIPS 2013</ref> | ||
| + | * The inner product function has [[nearest neighbor representation|nearest neighbor]] complexity bounded by <math>NN(f) \geq 2^{n/2}</math>. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Theorem 10</ref> | ||
| + | |||
| + | == Open questions == | ||
| + | * Is it true that Inner Product requires super-polynomial sized [[Circuit_complexity#AC0 | AC<sup>0</sup>]] circuits with parity gates? | ||
== References == | == References == | ||
<references/> | <references/> | ||
| + | |||
| + | [[Category:balanced function]] [[Category:even function]] | ||
Latest revision as of 09:25, 28 October 2020
Definition
A function [math]f:\{-1,1\}^{2k} \to \{-1,1\}[/math] is called an inner product function if it is equal to the sign of the inner product of the first half of the input and the second half. More formally,
[math]f(x_1,\ldots,x_k, y_1,\ldots,y_k) = (-1)^{\boldsymbol{x} \cdot \boldsymbol{y}}. [/math]
Properties
- TODO: Fourier representation
- The inner product function requires either exponential weights or an exponential number of nodes to be represented with a restricted Boltzmann machine. [1]
- The inner product function has nearest neighbor complexity bounded by [math]NN(f) \geq 2^{n/2}[/math]. [2]
Open questions
- Is it true that Inner Product requires super-polynomial sized AC0 circuits with parity gates?
References
- ↑ Theorem 9 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, On the Representational Efficiency of Restricted Boltzmann Machines, NIPS 2013
- ↑ Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Theorem 10
