On the complexity of approximating the VC dimension.
From MaRDI portal
Publication:1872731
DOI10.1016/S0022-0000(02)00022-3zbMath1059.68049OpenAlexW2156487206MaRDI QIDQ1872731
Elchanan Mossel, Christopher Umans
Publication date: 14 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00022-3
Related Items (6)
From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ A note on hardness of computing recursive teaching dimension ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ A PCP Characterization of AM ⋮ Extractors from Reed-Muller codes ⋮ The complexity of estimating min-entropy
Cites Work
- Unnamed Item
- On the density of sets of vectors
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Expanders, randomness, or time versus space
- Coordinate density of sets of vectors
- Extracting randomness: A survey and new constructions
- Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
- On limited nondeterminism and the complexity of the V-C dimension
- Extractors from Reed-Muller codes
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- List decoding algorithms for certain concatenated codes
- Privacy Amplification by Public Discussion
- Loss-less condensers, unbalanced expanders, and extractors
This page was built for publication: On the complexity of approximating the VC dimension.
