Let XRn and let be a class of functions mapping Rn−11 The famous VC-Theorem states that a random subset S of X of size O(d2logd), where d is the VC-Dimension of , is (with constant probability) an -approximation for with respect to the uniform distribution on X. In this work, we revisit the problem of constructing S explicitly. We show that for any XRn and any Boolean function class that is uniformly approximated by degree k, low-weight polynomials, an -approximation S can be be constructed deterministically in time poly(nk1X) . Previous work due to Chazelle and Matousek suffers an dO(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(nkX1) -time algorithm for deterministically constructing -approximations for circuits of size nk 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).