Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
cs.DM · cs.LG · math.CO
Quick verdict
Exact covering-design formulas and sharp probabilistic limits (11/20) for Boolean nearest-neighbour complexity; rigorous theory paper, partly incremental.
Summary
The paper studies how many labelled prototypes are needed so that nearest-neighbour classification reproduces a Boolean function on {0,1}^n, distinguishing prototypes allowed anywhere in R^n (NN(f)) from prototypes confined to the cube (BNN(f)). Three strands of results follow. Counting: a growth-function argument via Warren's theorem bounds labellings realisable with m real prototypes, giving VC dimension O(dm log m) — sharp in order for d >= 4 — and an almost-all lower bound k-NN(f) > 2^(n-1)/n^2 holding simultaneously for every voting number k; a direct count gives the stronger Boolean-prototype bound (c* - o(1))2^n with c* = 0.227092... the root of H2(c) + c = 1. Structure: the exact formula BNN(TH^n_t) = C(n, 2r-1, r) + 1 ties symmetric threshold functions to covering designs, yielding exponential rates, exact endpoint values (via Fort-Hedlund, Roedl, Keevash), disjunctive-lift formulas, and a characterisation of one-negative-prototype monotone representations. Probability: for a uniformly random function the normalised Boolean complexity concentrates near 1/2 or 1 with explicit limiting probabilities ((1 - e^(-1/2))^2 for the value 1), and for a random symmetric function it converges to 11/20 of the cube, whereas real prototypes need only (1/2 + o(1))n. Limitations: the uniform symmetric-function approximation carries a possibly removable log n/n factor, and several exact covering numbers remain open.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 1
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Almost every n-variable Boolean function requires more than 2^(n-1)/n^2 prototypes for every k-nearest-neighbour voting rule with real prototypes, and more than (c* - eps)2^n Boolean prototypes with c* = 0.227092... (Theorems 3.5, Corollary 3.7).
- The Boolean nearest-neighbour complexity of every symmetric threshold function is exactly C(n, 2r-1, r) + 1 with r = min{t, n-t+1} (Theorem 5.1).
- A non-constant monotone function admits a one-negative-prototype representation if and only if each At(f) is coverable by admissible rank-t blocks, with minimum size 1 + sum of kt(f) (Theorem 6.6).
- For a uniformly random Boolean function, BNN(Fn)/2^n concentrates near 1/2 or near 1 with explicit limiting probabilities, the value 1 occurring with probability (1 - e^(-1/2))^2 (Theorem 7.1).
- For a uniformly random symmetric function, BNN(Fn)/2^n converges to 11/20 in probability and in expectation, while real prototypes need only (1/2 + o(1))n (Theorem 8.5, citing [19]).
Strengths
Exact reduction to covering designs
Theorem 5.1 proves BNN(TH^n_t) = C(n, 2r-1, r) + 1 for every threshold level, converting an analytic problem into a classical design-theoretic quantity; Corollaries 5.4/5.6 then harvest Erdos-Spencer bounds, the rate rho(alpha) = H2(beta) - 2beta, Fort-Hedlund's exact C(n,3,2), Roedl asymptotics and Keevash design existence.
Sharp constants whose arithmetic is independently checkable
The closed form mu(theta) = theta^2(theta^2 - 5theta + 5)/(1 + theta - theta^2) (Lemma 8.6) evaluates to 11/20 at theta = 1/2 (verified by direct algebra), c* solves H2(c) + c = 1 (Corollary 3.7), and the limiting probability (1 - e^(-1/2))^2 approx 0.1548 in Theorem 7.1 follows from a clean Poisson(1/2) factorial-moment argument (Lemma 7.5).
Counting technology improved and made k-uniform
Reusable structural lemmas that unify prior work
Honest attribution and a precise open-problems section
Weaknesses
Partly incremental over prior work
Uniform approximation carries a log factor
Load-bearing dependence on deep external theorems
Disclosed LLM assistance in argument development
Sparse finite-n illustration
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This 56-page theory paper (arXiv 2609.23094v1; MSC primary 06E30, secondary 05B40/60C05/68Q32) studies prototype complexity of Boolean functions under nearest-neighbour classification: NN(f) with prototypes anywhere in R^n, BNN(f) with prototypes confined to {0,1}^n, and k-nearest-neighbour voting variants under the HLT separation convention. Its central claims: (i) an almost-all lower bound k-NN(f) > 2^(n-1)/n^2 valid simultaneously for every k (Theorem 3.5), built on a growth-function bound via Warren's theorem (Lemma 3.2; Corollary 3.3: V_{d,m} <= 2dm log2(16em^2), sharp in order for d >= 4); (ii) a direct count giving the Boolean-prototype lower bound (c* - o(1))2^n, c* = 0.227092... the root of H2(c) + c = 1 (Proposition 3.6, Corollary 3.7); (iii) the exact identity BNN(TH^n_t) = C(n, 2r-1, r) + 1 (Theorem 5.1) with disjunctive-lift and one-negative-prototype extensions (Theorems 6.2, 6.4, 6.6); (iv) limiting laws: BNN(Fn)/2^n near 1/2 or 1 with (1 - e^(-1/2))^2 for the value 1 (Theorem 7.1), and 11/20 of the cube for a uniformly random symmetric function (Theorem 8.5), against only (1/2 + o(1))n real prototypes [19].
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the difference between NN(f) and BNN(f) in this paper?
NN(f) is the minimum number of labelled prototypes placed anywhere in R^n whose nearest-neighbour classification matches the Boolean function f at every point of the cube {0,1}^n. BNN(f) additionally requires the prototypes themselves to be cube points. Requiring Boolean prototypes can make the minimum exponentially larger: e.g., some symmetric threshold functions need exponentially many Boolean prototypes but only 2 real ones when they are linear threshold functions.
What does the constant 11/20 mean in this paper?
For a uniformly random symmetric Boolean function (each Hamming layer label an independent fair bit), the minimum number of Boolean prototypes is asymptotically 11/20 of all 2^n cube points, both in probability and in expectation (Theorem 8.5). By contrast, with unrestricted real prototypes about n/2 prototypes suffice with high probability, so Boolean prototypes cost exponentially more in this random model.
How are covering designs connected to nearest-neighbour representations?
Theorem 5.1 proves BNN(TH^n_t) = C(n, 2r-1, r) + 1, where C(n, b, s) is the minimum number of b-subsets needed to cover every s-subset and r = min{t, n-t+1}. Classical covering-design results (Erdos-Spencer bounds, Rodl's asymptotics, Keevash's existence theorem, Fort-Hedlund exact values) then translate directly into exponential rates and exact prototype counts for symmetric threshold functions.
How hard is a typical random Boolean function for nearest-neighbour classification?
For a uniformly random function, the normalised Boolean prototype count is near 1 with probability (1 - e^(-1/2))^2, about 0.155, and near 1/2 otherwise, with probability about 0.845 (Theorem 7.1). In both regimes almost every function needs a constant fraction of the entire cube as Boolean prototypes.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The extracted text contains omitted passages ([...section omitted...]): Corollary 3.4, the formal statement of Theorem 7.1, Corollaries 5.9-5.11 (central window), and parts of the proofs of Theorem 8.3 and Lemma 8.8 could not be fully audited; their claims were cross-checked against the abstract, introduction, open-problems section and the surrounding proof text.
- Figure 1 is assessable only through its caption and the surrounding Example 8.2 discussion; no other figures appear.
- arXiv v1 (Sep 2026); no external peer-review status is stated.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.