2023/10/09 by Guorong Gao, Gao, Guorong, Jie Ma +5
Computer Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.2310.05353
openalex publication_date 2023/10/09 · openalex created_date 2023/10/13 · openalex updated_date 2026/07/28
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.