# Perceptron

## Definition

Let $n$ be a positive integer and let $t, \{w_i\}_{i=1}^n$ be real numbers. The perceptron function, or linear threshold function $f:\{-1,1\}^n \to \{-1,1\}$ with weights $w_i$ and threshold $t$ is defined as

 $f(x) = \begin{cases} 1, & \text{if} ~ \sum_i w_i x_i \geq t \\ -1 & \text{otherwise} \end{cases}$

The majority function is a special case of the perceptron, with threshold $t=0$ and all weights $w_i$ equal to each other.

## Properties

• If all weights are equal to each other, the function is symmetric.
• If all weights are non-negative, or all weights are non-positive, the function is monotone.
• The weights and threshold may be chosen so that the function is balanced.
• The perceptron is a special case of the polynomial threshold function.
• A perceptron has nearest neighbor complexity equal to $NN(f) = 2$. However, the Boolean nearest-neighbor complexity $BNN(f)$ can be high, e.g for the perceptron with all weights equal and $t = n/3$, then $2^{\Omega(n)}$ markers are required. [1]

## References

1. Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Theorem 4