The VC-Dimension of Axis-Parallel Boxes on the Torus

Abstract We show in this paper that the VC-dimension of the family of d-dimensional axis-parallel boxes and cubes on the d-dimensional torus are both asymptotically d log 2 ⁡ d . This is especially surprising as in most other examples the VC-dimension usually grows linearly with d in similar settings.