Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.05353 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912306051416064 |
|---|---|
| author | Gao, Guorong Ma, Jie Rong, Mingyuan Tran, Tuan |
| author_facet | Gao, Guorong Ma, Jie Rong, Mingyuan Tran, Tuan |
| contents | Since its introduction by Vapnik and Chervonenkis in the 1960s, the VC dimension and its variants have played a central role in numerous fields. In this paper, we investigate several variants of the VC dimension and their applications to dynamical systems. First, we prove a new bound for a recently introduced generalization of VC dimension, which unifies and extends various extremal results on the VC, Natarajan, and Steele dimensions. This new bound allows us to strengthen one of the main theorems of Huang and Ye [Adv. Math., 2009] in dynamical systems. Second, we refine a key lemma of Huang and Ye related to a variant of VC dimension by providing a more concise and conceptual proof. We also highlight a surprising connection among this result, combinatorics, dynamical systems, and recent advances in communication complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05353 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Variants of VC dimension and their applications to dynamics Gao, Guorong Ma, Jie Rong, Mingyuan Tran, Tuan Combinatorics Computational Complexity Dynamical Systems Since its introduction by Vapnik and Chervonenkis in the 1960s, the VC dimension and its variants have played a central role in numerous fields. In this paper, we investigate several variants of the VC dimension and their applications to dynamical systems. First, we prove a new bound for a recently introduced generalization of VC dimension, which unifies and extends various extremal results on the VC, Natarajan, and Steele dimensions. This new bound allows us to strengthen one of the main theorems of Huang and Ye [Adv. Math., 2009] in dynamical systems. Second, we refine a key lemma of Huang and Ye related to a variant of VC dimension by providing a more concise and conceptual proof. We also highlight a surprising connection among this result, combinatorics, dynamical systems, and recent advances in communication complexity. |
| title | Variants of VC dimension and their applications to dynamics |
| topic | Combinatorics Computational Complexity Dynamical Systems |
| url | https://arxiv.org/abs/2310.05353 |