VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions

2025/10/15 by F.-R. Chang, Chang, Fan, Yilin FANG +1
Computer Science · #Numerical Methods and Algorithms #Computability, Logic, AI Algorithms #Formal Methods in Verification

paper · pdf · doi:10.48550/arxiv.2510.13705

Abstract

In this paper, we uncover a new uncertainty principle that governs the complexity of Boolean functions. This principle manifests as a fundamental trade-off between two central measures of complexity: a combinatorial complexity of its supported set, captured by its Vapnik-Chervonenkis dimension (VC(f)), and its algebraic structure, captured by its polynomial degree over various fields. We establish two primary inequalities that formalize this trade-off: VC(f)+deg(f)≥ n, and VC(f)+deg_\mathbbF₂(f)≥ n. In particular, these results recover the classical uncertainty principle on the discrete hypercube, as well as the Sziklai--Weiner's bound in the case of \mathbbF₂.

Citations

• Maxmum Size of a Uniform Family with Bounded VC-dimension
• A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
• The VC-dimension of random subsets of finite groups
• Uniform set systems with small VC-dimension
• Sunflowers in set systems with small VC-dimension
• On t-Intersecting Families of Permutations
• Sunflowers in set systems of bounded dimension
• On the Zarankiewicz problem for graphs with bounded VC-dimension
• Approximation by juntas in the symmetric group, and forbidden intersection problems
• Bounded VC-dimension implies the Schur-Erdos conjecture
• Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
• Erdos-Hajnal conjecture for graphs with bounded VC-dimension
• Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós
• Harmonicity and invariance on slices of the Boolean cube
• Analysis of Boolean Functions
• Intersecting Families of Permutations
• Triangle-Intersecting Families of Graphs

Related

• VC-Dimension and Distance Chains in \mathbbF_q^d
• Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
• On the Rational Degree of Boolean Functions and Applications
• On the Probabilistic Degree of an n-variate Boolean Function
• On Separation between the Degree of a Boolean Function and the Block Sensitivity