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..