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
