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

CardsList
  1. Strategic PAC Learnability via Geometric Definability

    May 13, 2026Yuval Filmus, Shay Moran, Elizaveta Nesterova +2Singular Learning TheoryModel Complexity

  2. Contradiction Graphs Determine VC Dimension

    May 19, 2026Jesse Campbell, Daniel Ibaibarriaga, Lev ReyzinGraph TheoryProduct Spaces