An explicit VC-theorem for low-degree polynomials

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Let X ⊆ R n and let C be a class of functions mapping ℝ n → {-1,1}. The famous VC-Theorem states that a random subset S of X of size O(d/ε 2 log d/ε, where d is the VC-Dimension of C, is (with constant probability) an ε-approximation for C with respect to the uniform distribution on X. In this work, we revisit the problem of constructing S explicitly. We show that for any X ⊆ ℝ n and any Boolean function class C that is uniformly approximated by degree k polynomials, an ε-approximation S can be be constructed deterministically in time poly(n k,1/ε,|X|) provided that ε = Ω(W·√log|X|/|X|) where W is the weight of the approximating polynomial. Previous work due to Chazelle and Matousek suffers an d O(d) factor in the running time and results in superpolynomial-time algorithms, even in the case where k = O(1). We also give the first hardness result for this problem and show that the existence of a poly(n k,|X|,1/ε)-time algorithm for deterministically constructing ε-approximations for circuits of size n k for every k would imply that P∈=∈BPP. This indicates that in order to construct explicit ε-approximations for a function class , we should not focus solely on 's VC-dimension. Our techniques use deterministic algorithms for discrepancy minimization to construct hard functions for Boolean function classes over arbitrary domains (in contrast to the usual results in pseudorandomness where the target distribution is uniform over the hypercube).

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings
Pages495-504
Number of pages10
DOIs
StatePublished - Aug 28 2012
Event15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 - Cambridge, MA, United States
Duration: Aug 15 2012Aug 17 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7408 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012
CountryUnited States
CityCambridge, MA
Period8/15/128/17/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An explicit VC-theorem for low-degree polynomials'. Together they form a unique fingerprint.

  • Cite this

    Chattopadhyay, E., Klivans, A., & Kothari, P. (2012). An explicit VC-theorem for low-degree polynomials. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings (pp. 495-504). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS). https://doi.org/10.1007/978-3-642-32512-0_42