On the Complexity of Approximating the VC Dimension

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: •Σ3p-hard to approximate to within a factor 2−ε for all ε\u3e0,•approximable in AM to within a factor 2, and•AM-hard to approximate to within a factor N1−ε for all ε\u3e0. To obtain the Σ3p-hardness result we solve a randomness extraction problem using list-decodable binary codes; for the positive result we utilize the Sauer–Shelah(–Perles) Lemma. We prove analogous results for the q-ary VC dimension, where the approximation threshold is q