Tight Lower Bounds on the VC-dimension of Geometric Set Systems
Authors: Mónika Csikós, Nabil H. Mustafa, Andrey Kupavskii
JMLR 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: k-fold unions/intersections of half-spaces and the simplices set system. ... Our proofs are short and we make an effort to keep them self-contained. ... Section 3 contains the proof of Theorem 1 and Section 4 contains the proof of Theorem 2. |
| Researcher Affiliation | Academia | M onika Csik os EMAIL Nabil H. Mustafa EMAIL Universit e Paris-Est, LIGM, Equipe A3SI, ESIEE Paris, Cit e Descartes 2 boulevard Blaise Pascal, 93162 Noisy-le-Grand Cedex, France. Andrey Kupavskii EMAIL Laboratory of Advanced Combinatorics and Networks Applications, Moscow Institute of Physics and Technology, 9, Institutskiy per., Dolgoprudniy, 141701, Russia and Mathematical Institute, University of Oxford, Woodstock Rd, Oxford OX2 6GG, UK |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. It primarily focuses on mathematical proofs and theoretical derivations. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to code repositories. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs related to VC-dimension of geometric set systems. It does not use or refer to any experimental datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental datasets, hence there is no information regarding dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is purely theoretical, focusing on mathematical proofs and concepts. It does not describe any experiments that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational experiments or implementations, therefore, no software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper focuses on theoretical proofs and mathematical results; therefore, it does not include details about an experimental setup, hyperparameters, or training configurations. |