Let X is contained R~n and let C be a class of functions mapping R~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 is contained in R~n and any Boolean function class C that is uniformly approximated by degree k polynomials, an e-approximation S can be be constructed deterministically in time poly(n~k, 1/∈, |X|) provided that ∈ = Ω (W · log |X|/|X|~(1/2)) where W is the weight of the approximating polynomial. Previous work due to Chazelle and Ma-tousek 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 e-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 C, we should not focus solely on 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).
展开▼
机译：令X包含R〜n，令C为映射R〜n→{-1,1}的一类函数。著名的VC定理指出，X的随机子集S的大小为O（d /∈〜2 log d /∈），其中d是C的VC维，它以恒定的概率是C的∈近似值关于X上的均匀分布。在这项工作中，我们将重新讨论构造S的问题。我们证明，对于R中包含的任何X和由度k多项式统一逼近的布尔函数类C，可以在时间poly（n〜k，1 /∈，| | |中确定地构造e逼近S。 X |）假设∈=Ω（W·log | X | / | X |〜（1/2）），其中W是近似多项式的权重。 Chazelle和Ma-tousek所做的先前工作在运行时间上受到d〜（O（d））因子的影响，即使在k = O（1）的情况下，也会导致超多项式时间算法。我们还给出了该问题的第一硬度结果，并表明存在用于确定地构造大小为n〜k的电路每k的电子逼近的poly（n〜k，| X |，1 /∈）时间算法意味着P = BPP。这表明，为了构造函数类C的显式ε-逼近，我们不应该只关注C的VC维。我们的技术使用确定性算法来最小化差异，以在任意域上为布尔函数类构造硬函数（与通常的结果不同的是伪随机性，在伪随机性中目标分布在超立方体上是均匀的）。
展开▼
