VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909850096631808 |
|---|---|
| author | Chang, Fan Fang, Yijia |
| author_facet | Chang, Fan Fang, Yijia |
| contents | 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 ($\mathrm{VC}(f)$), and its algebraic structure, captured by its polynomial degree over various fields. We establish two primary inequalities that formalize this trade-off: $\mathrm{VC}(f)+\mathrm{deg}(f)\ge n,$ and $\mathrm{VC}(f)+\mathrm{deg}_{\mathbb{F}_2}(f)\ge 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 $\mathbb{F}_2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13705 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions Chang, Fan Fang, Yijia Combinatorics Computational Complexity Discrete Mathematics 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 ($\mathrm{VC}(f)$), and its algebraic structure, captured by its polynomial degree over various fields. We establish two primary inequalities that formalize this trade-off: $\mathrm{VC}(f)+\mathrm{deg}(f)\ge n,$ and $\mathrm{VC}(f)+\mathrm{deg}_{\mathbb{F}_2}(f)\ge 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 $\mathbb{F}_2$. |
| title | VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions |
| topic | Combinatorics Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2510.13705 |