Departmental Colloquium
Artem Chernikov
UCLA
Higher Vapnik-Chervonenkis theory
Abstract: Finite VC-dimension, a combinatorial property of families of sets, was discovered simultaneously by Vapnik and Chervonenkis in probabilistic learning theory, and by Shelah in model theory (where it is called NIP). It plays an important role in several areas including machine learning, combinatorics, mathematical logic, functional analysis and topological dynamics. We develop aspects of higher-order VC-theory, establishing a higher arity generalization of the epsilon-net theorem for sets (and functions) with bounded VC_k-dimension. As an application, we obtain a strong version of Szemerédi's regularity lemma for hypergraphs omitting a fixed finite k-partite k-hypergraph. Joint work with Henry Towsner.
Friday October 14, 2022 at 3:00 PM in Library Conference Room 1-470