CaltechAUTHORS
  A Caltech Library Service

On the Complexity of Approximating the VC dimension

Mossel, Elchanan and Umans, Christopher (2001) On the Complexity of Approximating the VC dimension. In: 16th Annual IEEE Conference on Computational Complexity Proceedings. Annual IEEE Conference on Computational Complexity. IEEE Computer Society , Los Alamitos, CA, pp. 220-225. ISBN 0-7695-1054-X. https://resolver.caltech.edu/CaltechAUTHORS:20111118-115638180

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111118-115638180

Abstract

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: Σ_3^p-hard to approximate to within a factor 2-ε for any ε>0; approximable in AM to within a factor 2; and AM-hard to approximate to within a factor N_ε for some constant ε>0. To obtain the Σ_3^p-hardness results we solve a randomness extraction problem using list-decodable binary codes; for the positive results we utilize the Sauer-Shelah(-Perles) Lemma. The exact value of ε in the AM-hardness result depends on the degree achievable by explicit disperser constructions.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/CCC.2001.933889DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=933889PublisherUNSPECIFIED
Additional Information:© 2001 IEEE. Date of Current Version: 07 August 2002. We thank Gil Kalai for helpful discussions and Adam Smith for a useful reference.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number6998461
Series Name:Annual IEEE Conference on Computational Complexity
Record Number:CaltechAUTHORS:20111118-115638180
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20111118-115638180
Official Citation:Mossel, E.; Umans, C.; , "On the complexity of approximating the VC dimension," Computational Complexity, 16th Annual IEEE Conference on, 2001. , vol., no., pp.220-225, 2001 doi: 10.1109/CCC.2001.933889 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=933889&isnumber=20210
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27860
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:21 Nov 2011 00:02
Last Modified:03 Oct 2019 03:27

Repository Staff Only: item control page