Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
The Parameterized Complexity of Computing the VC-Dimension
Authors: Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney, Prafullkumar Tale
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph H = (V, E), we prove that the naive 2O(|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 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 2O(tw log tw) |V |-time algorithm for any graph G = (V, E) of treewidth 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). |
| Researcher Affiliation | Collaboration | Florent Foucaud Université Clermont Auvergne, CNRS, Mines Saint-Étienne, Clermont Auvergne INP, LIMOS Clermont-Ferrand, France EMAIL Harmender Gahlawat Université Clermont Auvergne, CNRS, Mines Saint-Étienne, Clermont Auvergne INP, LIMOS Clermont-Ferrand, France EMAIL Fionn Mc Inerney Telefónica Scientific Research Barcelona, Spain EMAIL Prafullkumar Tale Indian Institute of Science Education and Research Pune Pune, India EMAIL |
| Pseudocode | No | The paper describes algorithms and their theoretical running times, particularly in Sections 4 and 5 (e.g., dynamic programming on tree-decomposition), but it does not present any formal pseudocode blocks or algorithms labeled as such. The algorithmic descriptions are integrated into the paragraph text. |
| Open Source Code | No | The paper does not include experiments. The paper does not provide open access to data and code. No mention of code availability, repositories, or supplementary materials containing code is made. |
| Open Datasets | No | The paper does not include experiments. The paper is theoretical in nature and does not use or reference any datasets for empirical validation. |
| Dataset Splits | No | The paper does not include experiments. As the paper is theoretical and does not use datasets for empirical validation, there is no discussion of dataset splits. |
| Hardware Specification | No | The paper does not include experiments. The research is theoretical, focusing on computational complexity, and therefore does not involve running experiments on specific hardware. |
| Software Dependencies | No | The paper does not include experiments. The research is theoretical and does not describe any specific software dependencies or versions required to replicate experimental results. |
| Experiment Setup | No | The paper does not include experiments. As the paper presents theoretical results and algorithms, it does not detail any experimental setups, hyperparameters, or training configurations. |