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: Σ₃^p-hard to approximate to within a factor 2-ε for any ε>0; approximable in Aℳ to within a factor 2; and Aℳ-hard to approximate to within a factor N^ε for some constant ε>0. To obtain the Σ₃⁹-hardness results we solve a randomness extraction problem using list-decodable binary codes; for the positive results we utilize the Sauer-Shelah(-Perles) Lemma. The exact value of ε in the Aℳ-hardness result depends on the degree achievable by explicit disperser constructions