Published June 2001
| public
Book Section - Chapter
On the Complexity of Approximating the VC dimension
- Creators
-
Mossel, Elchanan
- Umans, Christopher
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.
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.Additional details
- Eprint ID
- 27860
- DOI
- 10.1109/CCC.2001.933889
- Resolver ID
- CaltechAUTHORS:20111118-115638180
- Created
-
2011-11-21Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- Annual IEEE Conference on Computational Complexity
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 6998461