Inapproximability of VC Dimension and Littlestone’s Dimension
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:14321460, 2017.
Abstract
We study the complexity of computing the VC Dimension and Littlestone’s Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x,C)$th entry is $1$ iff element $x$ belongs to concept $C$), both can be computed exactly in quasipolynomial time ($n^O(\log n)$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove nearly matching lower bounds on the running time, that hold even for \em approximation algorithms.
Related Material


