View source for 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 function|symmetric]], then <math>NN(f) \leq n + 1</math>. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Proposition 3</ref>
* If <math>f</math> is a [[Linear threshold|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>. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Theorem 5</ref>

== 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>. <ref>Péter Hajnal, Zhihao Liu, György Turán, [https://arxiv.org/pdf/2004.01741.pdf Nearest neighbor representations of Boolean functions], Lemma 9</ref>

== References ==
<references/>