We establish new results on the complexity of computing the VC-dimension, including fixed-parameter algorithms and running time lower bounds under the Exponential Time Hypothesis.

We show that for nxn Boolean matrices with VC-dimension d, we can do matrix-vector multiplication in O(n^{2-1/d}) time, and provide a number of applications and extensions of this result..