Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-127 | 3rd October 2012 05:16

An Explicit VC-Theorem for Low-Degree Polynomials


Authors: Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari
Publication: 3rd October 2012 18:27
Downloads: 1984


Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal 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 \subseteq \mathbb{R}^{n}$ and any Boolean function class ${\mathcal C}$ that is uniformly approximated by degree $k$, low-weight polynomials, an $\epsilon$-approximation $S$ can be be constructed deterministically in time $poly(n^{k},1/\epsilon,|X|)$. 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/\epsilon)$-time algorithm for deterministically constructing $\epsilon$-approximations for circuits of size $n^k$ for every $k$ would imply that P = BPP. This indicates that in order to construct explicit $\epsilon$-approximations for a function class ${\mathcal C}$, we should not focus solely on ${\mathcal C}$'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).

ISSN 1433-8092 | Imprint