Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
复制标题
DOI：
10.1007/978-3-662-47672-7_22
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Mark Bun;J. Thaler
中科院分区：
文献类型：
--
作者：
Mark Bun;J. Thaler
我们建立了硬度放大的通用形式，用于通过多项式逼近恒定深度布尔电路。具体来说，我们表明，如果布尔电路不能通过低次多项式在某种单方面意义上的恒定误差内逐点近似，那么即使误差非常高，该电路的不相交副本的“或”也不能逐点近似。作为我们的主要应用，我们证明对于每个度序列，都存在一个显式的多项式大小的深度三电路，使得任何度多项式都不能更好地逐点逼近误差。作为我们主要结果的结果，我们获得了 AC 中函数差异的上限和 AC 阈值权重的下界，分别改进了 和 之前的最佳结果。我们的技术还产生了 AND-OR 深度树的近似程度的新下界，该下界与任何常数的多对数因子紧密相关，以及一次性读取 DNF 公式的新界限。反过来，这些结果意味着这些类别的通信和电路复杂性的新下限，并表明现有 PAC 学习算法的强大局限性。
We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit cannot be pointwise approximated even with very high error. As our main application, we show that for every sequence of degrees, there is an explicit depth-three circuitof polynomial-size such that any degree-polynomial cannot pointwise approximateto error better than. As a consequence of our main result, we obtain anupper bound on the the discrepancy of a function in AC, and anlower bound on the threshold weight of AC, improving over the previous best results ofandrespectively.Our techniques also yield a new lower bound ofon the approximate degree of the AND-OR tree of depth, which is tight up to polylogarithmic factors for any constant, as well as new bounds for read-once DNF formulas. In turn, these results imply new lower bounds on the communication and circuit complexity of these classes, and demonstrate strong limitations on existing PAC learning algorithms.