Counting and Covering in Nearest-Neighbour Representations of Boolean Functions

Martin Anthony

cs.DMSep 19, 2026

Counting and Covering in Nearest-Neighbour Representations of Boolean Functions

Authors: Martin Anthony

Organizations: Department of Mathematics London School of Economics and Political Science, London, UK

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Layer structure for the function in Example 8.2 . Boundary $i$ lies between layers $i-1$ and $i$ ; it is a transition when $D_{i}=1$ . The bookkeeping values $D_{0}=D_{9}=1$ are not shown. The isolated transitions $2$ and $4$ form the single edge of $G_{f}$ . A minimum-weight vertex cover selects $2$ (shaded), choosing layers $1,2$ . The consecutive transitions $7,8$ force the complete layers $\mathcal{H}=\{6,7,8\}$ (heavy outlines). Braces mark the constant runs. These complete layers give the lower bound $W_{8}(f)=37+36=73$ ; the example shows why another $20$ prototypes are needed.

VC Dimension

See all 9 papers

Jun 28, 2026

Chamber geometry and specification numbers of Boolean threshold functions

The specification number

σ_n(f)

of a Boolean threshold function

f

n

variables is the least number of points whose

f

-values determine

f

uniquely among all threshold functions. Its essential points form the unique minimum such set. We develop Zuev's geometric interpretation: the threshold functions are the chambers of a central hyperplane arrangement in the

(n+1)

-dimensional space of weights and thresholds, and the essential points of a function correspond exactly to the facets of its chamber, so the specification number is the chamber's facet number. The lower bound

σ_n(f)\ge n+1

becomes the fact that a pointed full-dimensional cone has at least

n+1

facets, with equality for simplicial chambers. The average specification number

\overlineσ_n

becomes an average facet count. We evaluate this average exactly via the resonance arrangement and bound it through a theorem of Fukuda, Tamura, and Tokuyama, obtaining

\overlineσ_n\le 2n

; hence

\overlineσ_n=Θ(n)

. This settles a question of Gutekunst, Mészáros, and Petersen. The method also extends to polynomial threshold functions. The same geometry links threshold functions with a threshold zonotope, whose vertices are modified Chow vectors. Its one-skeleton is the one-inclusion graph, and a vertex's degree is the specification number of that function. Finally, we treat the operations of Lozin et al. on functions of minimum specification number. Adding a variable and extending on a variable both take the product of a chamber closure with a half-line, preserving simpliciality. For the symmetric-variables extension we give an exact thresholdness criterion and show that minimum specification number is preserved whenever the extension is a threshold function. We also resolve a question they pose concerning a fourth operation.

Martin Anthony

Department of Mathematics, London School of Economics

Boolean Function Learning

Ask PDF

May 21, 2026

Holographic functions and neural networks

A fuzzy Boolean function is a map

f:\cube^n\to [0,1]

, where

n\in\mathbb N

. We introduce and compare three ways of saying that such a function has bounded complexity. The first is a sampling property: the value

f(x)

can be recovered, up to small error and with high probability, from the values of a bounded number of randomly chosen coordinates of

x

. We call this the holographic property. The second is a structural property:

f

is uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms. The third is computational:

f

is uniformly close to the output of a neural network with a bounded number of non-input neurons, bounded Lipschitz activation functions and bounded incoming weights. We prove that these three properties are equivalent up to quantitative changes of the parameters. The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.

Balazs Szegedy

Neural Network Approximation Theory Neural Network Expressivity

Ask PDF

Sep 24, 2026

Boolean threshold functions, neuron capacity, and memory retrieval

How much information can a single neuron remember? How many memories can neural networks retrieve without creating false memories? These questions are related to a basic question: how many Boolean threshold functions

f(x)=\operatorname{sgn}(a_0+\langle a,x\rangle)

x\in\{-1,1\}^n

, are there? In this paper, we show that the number

T_n

of distinct Boolean threshold functions is

T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr).

Equivalently, the capacity of a single threshold neuron is

n^2-\log_2(n!)+1+O(n^{-99})

bits, improving the

O(n)

error term in the result of Kahn--Komlós--Szemerédi to

O(n^{-99})

. To prove this, we show that, for

1\le r\le n-1

, and

v_1,\ldots,v_r

are chosen at random from

\{-1,1\}^n

\mathbb P\!\left\{ \langle v_1,\ldots,v_r\rangle\cap\{-1,1\}^n =\{\pm v_1,\ldots,\pm v_r\} \right\} =1-O(n^{-99}).

In the context of the Kanter--Sompolinsky Hamiltonian for memory retrieval, this identifies

r=n-1

as a sharp threshold, at which, for almost every collection of

r

memories, the only ground states are these memories and their negatives, confirming a weaker form of the Kalai--Linial--Odlyzko conjecture. It also settles a recent open problem posed by M. Anthony on the specification number of Boolean threshold functions. In addition, we show that, for every

1\le r\le n-1

\mathbb P\{v_1,\ldots,v_r\text{ are linearly dependent}\} =2\binom r2\,2^{-n}+O\!\left(2^{-n}e^{-cn}\right),

confirming a conjecture of Kahn--Komlós--Szemerédi.

Xinyuan Xie

Boolean Function Learning Neural Network Memorization Associative Memory

Ask PDF

Abstract

VC Dimension

Explore similar work

Chamber geometry and specification numbers of Boolean threshold functions

Holographic functions and neural networks

Boolean threshold functions, neuron capacity, and memory retrieval