cs.AIAug 3, 2026

Hypercubes, Hyperplanes, and Constraint-Induced Complexity Collapse in Atomic Concept Learning

Authors: Irene Tsapara

Organizations: National University, San Diego, United States

Abstract

We revisit higher-arity atomic concept learning through the geometry of hypercubes and hyperplanes of ground instances. Our starting point is the observation that the ambient r-dimensional hypercube of ground atoms is not structurally uniform. Its logical complexity is organized by hyperplanes: every hyperplane other than the full diagonal collapses into finitely many elementary-equivalence classes, with a bound independent of the term depth, while the full diagonal is exceptional and its class count grows without bound. This asymmetry is not merely geometric. It reflects the reduction-theoretic structure of the concepts themselves. Building on a higher-dimensional framework developed in the author's earlier work, we reinterpret these results through canonical simple concepts, minimal orderings, and representative reductions. This yields a taxonomy of hyperplane behavior in higher dimensions and shows that complexity is localized rather than spread uniformly through the instance space. The paper includes a fully worked binary case, an explicit treatment of the ternary hypercube, and an unpacked account of the reduction machinery that drives the collapse. The three-dimensional case already exhibits the essential phenomenon of orthogonal families, partial diagonals, and the exceptional full diagonal. This geometric-logical perspective clarifies where complexity is concentrated in atomic concept learning and suggests a modern interpretation in terms of constrained hypothesis spaces and structured classification.

Explore similar work

Jun 16, 2026cs.LG

Sign-Rank, Index, and List Replicability: Connections and Separations

In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the Z2\mathbb{Z}_2-index and the list replicability number. We order these measures, showing that the Z2\mathbb{Z}_2-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and Z2\mathbb{Z}_2-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.
Ari Blondal, Hamed Hatami, Pooya Hatami +2
May 13, 2026cs.LG

Strategic PAC Learnability via Geometric Definability

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension 11 on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over Rexp\mathbb{R}_{\mathtt{exp}}. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including p\ell_p distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.
Yuval Filmus, Shay Moran, Elizaveta Nesterova +2
May 19, 2026stat.ML

Contradiction Graphs Determine VC Dimension

We study the contradiction graphs associated with binary concept classes. For a class H{0,1}XH \subseteq \{0,1\}^X, the order-mm contradiction graph Gm(H)G_m(H) has as vertices the HH-realizable labeled sequences of length mm, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. Our main result is that the single graph Gm(H)G_m(H) determines the threshold predicate VCdim(H)m\mathrm{VCdim}(H)\ge m. Consequently, the full sequence (Gm(H))m1(G_m(H))_{m \ge 1} determines the exact VC dimension and, in particular, detects finite versus infinite VC dimension, answering a question posed by Alon et al. (2024).
Jesse Campbell, Daniel Ibaibarriaga, Lev Reyzin