# Nearest neighbor representation

## General

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

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

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

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

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

Trivially, [math]NN(f) \leq BNN(f) \leq 2^n[/math].

## Properties

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

## Relation to other complexity measures

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

## References

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