Andrey Kupavskii VC-dimension of polytopes | MLC '20

The talk by Andrey Kupavskii (MIPT, Moscow, Russia and CNRS, Grenoble, France) “VC-dimension of polytopes“ that he made on the conference “Machine Learning and Combinatorics 2020“ at MIPT. Abstract: We discuss recent progress in the questions on the VC-dimension of d-dimensional polytopes with k facets / k vertices. For the former class, we determine the order of growth of the VC-dimension, which turns out to be superlinear in k (joint with Csicos and Mustafa). For the latter class, we show the first polynomial upper bound on the VC-dimension.