On the complexity of approximating the VC dimension.

DOI10.1016/S0022-0000(02)00022-3MaRDI QIDQ1872731zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

complexity of approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions
• On limited nondeterminism and the complexity of the V-C dimension
• An explicit VC-theorem for low-degree polynomials

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Coordinate density of sets of vectors
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• Expanders, randomness, or time versus space
• Extracting randomness: A survey and new constructions
• Extractors from Reed-Muller codes
• scientific article; zbMATH DE number 895368 (Why is no real title available?)
• List decoding algorithms for certain concatenated codes
• Loss-less condensers, unbalanced expanders, and extractors
• On limited nondeterminism and the complexity of the V-C dimension
• On the density of families of sets
• On the density of sets of vectors
• Privacy Amplification by Public Discussion
• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources

Cited in

(11)

• 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
• The complexity of estimating min-entropy
• A PCP characterization of AM
• An explicit VC-theorem for low-degree polynomials
• Increasing the Output Length of Zero-Error Dispersers
• On the VC-dimension of binary codes
• From undecidability of non-triviality and finiteness to undecidability of learnability
• A note on hardness of computing recursive teaching dimension
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions

This page was built for publication: On the complexity of approximating the VC dimension.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1872731)