# Nearest neighbor representation

## General

A nearest-neighbor representation of a Boolean function $f:\{-1,1\}^n \to \{-1,1\}$ is a pair of disjoint subsets $(P,N)$ of $\mathbb{R}^n$ such that for every $x \in \{-1,1\}^n$ there is a unique point in $P \cup N$ closest to $x$, and $f(x) = 1$ iff this closest point is in $P$.

Informally, we think of $P$ as "positive markers" and $N$ as "negative markers"; $f$'s value is determined by the closest marker.

The k-nearest-neighbor representation takes majority among the closest $k$ points: $f(x) = 1$ iff the majority of the closest $k$ points are in $P$.

The markers in the nearest-neighbor representations may also be constrained to lie in the cube $\{-1,1\}^n$; in this case, we call the representation a Boolean nearest-neighbor representation.

The minimal number of markers $|P \cup N|$ required to represent a function is called its nearest neighbor complexity, and denoted by $NN(f)$. If all markers are constrained to lie in the cube, we call this the Boolean nearest neighbor complexity, and denote it by $BNN(f)$.

Trivially, $NN(f) \leq BNN(f) \leq 2^n$.

## Properties

• If $f$ is symmetric, then $NN(f) \leq n + 1$. [1]
• If $f$ is a linear threshold function, then $NN(f) = 2$.
• In general, $NN(f) \leq \left( 1 + o(1)\right) 2^{n+2} /n$. [2]

## Relation to other complexity measures

• If $f$ has a nearest neighbor representation with $m$ markers, then there is a polynomial $p : \{1,2\}^n \to \mathbb{R}$ with $m$ terms such that $p(x) \geq 0 \iff f(x) = 1$. [3]

## References

1. Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Proposition 3
2. Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Theorem 5
3. Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Lemma 9