# Inner product

## Definition

A function $f:\{-1,1\}^{2k} \to \{-1,1\}$ 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,

 $f(x_1,\ldots,x_k, y_1,\ldots,y_k) = (-1)^{\boldsymbol{x} \cdot \boldsymbol{y}}.$

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

## Open questions

• Is it true that Inner Product requires super-polynomial sized AC0 circuits with parity gates?

## References

1. Theorem 9 in James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard Zemel, On the Representational Efficiency of Restricted Boltzmann Machines, NIPS 2013