Redirecting to original paper in 30 seconds...
Click below to go immediately or wait for automatic redirect
📄 Abstract
Abstract: The VC-dimension is a well-studied and fundamental complexity measure of a
set system (or hypergraph) that is central to many areas of machine learning.
We establish several new results on the complexity of computing the
VC-dimension. In particular, given a hypergraph
$\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive
$2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under
the Exponential Time Hypothesis (ETH). We then prove that the problem admits a
$1$-additive fixed-parameter approximation algorithm when parameterized by the
maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when
parameterized by its dimension, and that these are essentially the only such
exploitable structural parameters. Lastly, we consider a generalization of the
problem, formulated using graphs, which captures the VC-dimension of both set
systems and graphs. We design a $2^{\mathcal{O}(\rm{tw}\cdot \log
\rm{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth
$\rm{tw}$ (which, for a set system, applies to the treewidth of its incidence
graph). This is in contrast with closely related problems that require a
double-exponential dependency on the treewidth (assuming the ETH).
Authors (4)
Florent Foucaud
Harmender Gahlawat
Fionn Mc Inerney
Prafullkumar Tale
Submitted
October 20, 2025
Key Contributions
This paper establishes tight lower bounds on the complexity of computing the VC-dimension under the ETH, proving the $2^{\mathcal{O}(|\mathcal{V}|)}$ algorithm is asymptotically optimal. It also presents fixed-parameter algorithms parameterized by maximum degree and dimension, and introduces a generalized graph-based formulation.
Business Value
Contributes to the fundamental understanding of machine learning complexity, which can indirectly inform the design of more efficient algorithms and better theoretical guarantees for ML models.