# Boolean Nearest Neighbor Language in the Knowledge Compilation Map

arXiv: https://arxiv.org/abs/2410.06332 · HTML: https://mlsanity.com/paper/2410.06332/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 22 references that are in the map.
- First posted on arXiv 8 Oct 2024.

## Builds on (most cited first, 3 of 3)

- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [Near-optimal sample compression for nearest neighbors](https://mlsanity.com/paper/1404.3368/) (2014)
- [On the Information Capacity of Nearest Neighbor Representations](https://mlsanity.com/paper/2305.05808/) (2023)

## Abstract (arXiv)

The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turan. A BNN representation of f is a pair (P,N) of sets of Boolean vectors (called positive and negative prototypes) where f(x)=1 for every positive prototype x ∈ P, f(x)=0 for all every negative prototype x ∈ N, and the value f(x) for x not∈ P cup N is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we derive results which compare the succinctness of the BNN language to several standard languages from KCM, and determine the complexity status of most standard queries and transformations for BNN inputs.