Artem Chernikov : Higher Vapnik-Chervonenkis theory

Posted by Marcus Michelen , part of the Departmental Colloquium.

At

Oct. 14, 2022, 3 p.m.

In

Library Conference Room 1-470

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.