Metraipolis › archive › dc_ccae2c4c8a31

Counting and Covering in Nearest-Neighbour Representations of Boolean Functions — arXiv:2609.23094

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.23094
License (as archived): CC0-1.0
Archived: 2026-10-09T07:08:23.342Z
SHA-256 of the archived text: 1e3da5c3752d5c358dc84c9157b19ed2f16f6f6cbbf40dbde693fb9a51e19de1
Stable URL of this page: https://metraipolis.com/documento/dc_ccae2c4c8a31

How to cite

Counting and Covering in Nearest-Neighbour Representations of Boolean Functions — arXiv:2609.23094 — arXiv (en), https://arxiv.org/abs/2609.23094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ccae2c4c8a31 (Metraipolis archive dc_ccae2c4c8a31, sha256 1e3da5c3752d5c358dc84c9157b19ed2f16f6f6cbbf40dbde693fb9a51e19de1)

BibTeX

@misc{dcccae2c4c8a31,
  title = {Counting and Covering in Nearest-Neighbour Representations of Boolean Functions — arXiv:2609.23094},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.23094},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ccae2c4c8a31; sha256 1e3da5c3752d5c358dc84c9157b19ed2f16f6f6cbbf40dbde693fb9a51e19de1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23094. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification. There are two distinct settings: the prototypes may be arbitrary points of Euclidean space, or they may themselves be required to lie in the Boolean cube. For unrestricted prototypes, we strengthen a known lower bound for almost all Boolean functions. The bound applies simultaneously to nearest-neighbour voting rules with any number of voting neighbours, and substantially narrows the gap with the known general upper bound. We obtain a VC-dimension bound for classes with a bounded number of prototypes, and show that it is sharp in order in dimensions at least four. We then study Boolean prototypes, beginning with symmetric threshold functions. A connection with covering designs expresses the minimum number of prototypes at every threshold level exactly in terms of a covering number, and leads to further exact results for related monotone functions, including disjunctive extensions and a characterisation of when a representation with a single negative prototype is possible. For a uniformly random Boolean function, the Boolean nearest-neighbour complexity, as a proportion of the cube, is asymptotically close either to one half or to one, with explicit limiting probabilities. In particular, almost every Boolean function requires at least approximately half as many prototypes as there are points in the cube, and one half is the largest proportion for which such a lower bound holds. Finally, we consider arbitrary symmetric Boolean functions. Their Boolean nearest-neighbour complexity is closely approximated by a weighted vertex-cover problem on paths. As a consequence, a uniformly random symmetric function typically requires prototypes amounting to $11/20$ of the cube. This is much larger than the upper bounds known when the prototypes are allowed to lie anywhere in Euclidean space.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-22 in cs.LG).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Machine Learning (cs.LG); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.23094 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T06:58:09.553Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).