An Explicit VC-Theorem for Low-Degree Polynomials
An Explicit VC-Theorem for Low-Degree Polynomials
复制标题
低次多项式的显式 VC 定理
DOI：
10.1007/978-3-642-32512-0_42
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Pravesh Kothari
中科院分区：
文献类型：
--
作者：
Eshan Chattopadhyay;Adam R. Klivans;Pravesh Kothari
LetX≥Rnand≥一类映射到∈n→{−1,1}的函数。著名的vc -定理指出，大小的随机子集sofx，其中的vc维，是（以恒定的概率）关于x上的均匀分布的ε-近似。在这项工作中，我们重新审视了显式构造的问题。我们证明了对于任意X的任一个被次多项式统一近似的布尔函数类，在时间多项式（nk,1/ε,|X|）中可以确定性地构造一个ε-近似，其中为近似多项式的权值。Chazelle和Matousek之前的工作在运行时间上受到一个do (d)因素的影响，即使在week =O(1)的情况下，也会产生超多项式时间算法。我们还给出了该问题的第一个硬度结果，并证明了用于确定构造sizek for everyk电路的ε-近似的apoly（nk,|X|,1/ε）时间算法的存在性，这意味着p =BPP。这表明，为了构造函数类的显式近似，我们不应该只关注vc维。我们的技术使用确定性算法来最小化差异，为布尔函数类的超任意域构造硬函数（与目标分布在超立方体上均匀的伪随机性的通常结果相反）。
LetX⊆Rnand letbe a class of functions mapping ℝn→ { − 1,1}. The famous VC-Theorem states that a random subsetSofXof size, wheredis the VC-Dimension of, is (with constant probability) anε-approximation forwith respect to the uniform distribution onX. In this work, we revisit the problem of constructingSexplicitly. We show that for anyX⊆ ℝnand any Boolean function classthat is uniformly approximated by degreekpolynomials, anε-approximationScan be be constructed deterministically in timepoly(nk,1/ε,|X|) provided thatwhereWis the weight of the approximating polynomial. Previous work due to Chazelle and Matousek suffers andO(d)factor in the running time and results in superpolynomial-time algorithms, even in the case wherek=O(1).We also give the first hardness result for this problem and show that the existence of apoly(nk,|X|,1/ε)-time algorithm for deterministically constructingε-approximations for circuits of sizenkfor everykwould imply thatP=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 overarbitrarydomains (in contrast to the usual results in pseudorandomness where the target distribution is uniform over the hypercube).