  A nearest neighbor representation of a Boolean function is a set of positive
and negative prototypes in $R^n$ such that the function has value 1 on an input
iff the closest prototype is positive. For $k$-nearest neighbor representation
the majority classification of the $k$ closest prototypes is considered. The
nearest neighbor complexity of a Boolean function is the minimal number of
prototypes needed to represent the function. We give several bounds for this
measure. Separations are given between the cases when prototypes can be real or
are required to be Boolean. The complexity of parity is determined exactly. An
exponential lower bound is given for mod 2 inner product, and a linear lower
bound is given for its $k$-nearest neighbor complexity. The results are proven
using connections to other models such as polynomial threshold functions over
$\{1, 2\}$. We also discuss some of the many open problems arising.
