On the complexity of approximating the VC dimension.
type: Item
instance of: scholarly article
title: On the complexity of approximating the VC dimension.
zbMATH Open document ID: 1059.68049
DOI: 10.1016/S0022-0000(02)00022-3
author: Elchanan Mossel
author: Christopher Umans
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1910855
zbMATH Keywords: complexity of approximation
MaRDI profile type: Publication
cites work: On the density of sets of vectors
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Privacy Amplification by Public Discussion
cites work: List decoding algorithms for certain concatenated codes
cites work: Coordinate density of sets of vectors
cites work: Q4883380
cites work: Extracting randomness: A survey and new constructions
cites work: On limited nondeterminism and the complexity of the V-C dimension
cites work: On the density of families of sets
cites work: Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: Expanders, randomness, or time versus space
cites work: Loss-less condensers, unbalanced expanders, and extractors
cites work: Extractors from Reed-Muller codes
cites work: Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
full work available at URL: s0022-0000(02)00022-3
OpenAlex ID: W2156487206
description: scientific article; zbMATH DE number 1910855