COVER’S THEOREM AND THE SET-SEPARATION PROBLEM VIA POLYNOMIAL THRESHOLD FUNCTIONS (PTFS)

Abstract

Separating subsets of points in Euclidean space is a foundational problem in data analysis and neurocomputing; its solvability crucially depends on the class of admissible decision boundaries. Linear models are sharply limited (for three variables, only 104 out of 256 dichotomies are linearly separable), which motivates the transition to nonlinear approaches. This article presents a complete combinatorial catalogue of all 256 possible separations of the cube’s vertices and precisely quantifies the limits of separability by second-degree polynomials. The authors show that, among the 22 unique equivalence classes (orbits) of dichotomies with respect to the cube’s symmetry group, exactly one class is not quadratically separable. This analysis not only provides an exhaustive answer to the question posed, but also illustrates fundamental constraints inherent  even to powerful nonlinear models when operating on highly structured data.To this end, we exploit an isomorphism between the geometric separation problem and the algebraic problem of realizing Boolean functions. Each dichotomy of the cube’s vertices corresponds uniquely to a Boolean function of three variables, and the question of quadratic separability becomes equivalent to asking whether the given function is a polynomial threshold function of degree two. The result yields an exact boundary on the expressive power of quadratic threshold elements for binary classification tasks in low dimensions and explains why moving from linear to quadratic models already leads to a dramatic increase in classification capability. The authors’ result establishes the precise limit of the separating power of degree-two polynomial threshold functions (PTF-2) for binary classification in low-dimensional regimes and explains why the transition from linear to quadratic models already markedly enhances classification capacity. The presented asymptotic estimates indicate that, in highdimensional settings and for a fixed polynomial degree, the proportion of separable dichotomies declines rapidly. This underscores the intrinsic difficulty of high-dimensional spaces and provides a theoretical rationale for developing alternative neural-network models and  architectures.