{"id":"arxiv/2609.23094","url":"https://arxiv.org/abs/2609.23094","tags":["cs.DM","cs.LG","math.CO"],"score":0,"title":"Counting and Covering in Nearest-Neighbour Representations of Boolean Functions","domain":"cs.DM","source":"arxiv","authors":["Martin Anthony"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-19","reactions":{}}