Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
复制标题
深度二和深度三阈值电路的超线性门和超二次线下界
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
D. Kane;Ryan Williams
为了正式理解神经计算的能力，我们首先需要破解两层和三层阈值电路的前沿，这是一种令人惊讶的难以分析的机制。我们证明了第一个超线性门下界和第一个超二次线下界的深度为2的线性阈值电路的任意权重，和深度为3的多数电路计算一个显式函数。(1)我们证明了对于所有的ε log（n）/n，线性时间可计算的Andreev函数不能用o（ε3 n3/2/log 3 n）门的深度2电路在n位输入的（1/2+ε）分数上计算，也不能用o（ε3 n5/2/log 7/2 n）线计算.这为阈值电路建立了一个平均情况下的“大小层次”，因为Andreev函数可以通过O（n）个线性阈值门的均匀深度2电路和O（n）个多数门的均匀深度3电路来计算。(2)我们提出了一个新的功能在P的小偏置集的基础上，我们证明了不能计算的深度为2阈值电路的O（n3/2/log 3 n）门的多数表决，也与O（n5/2/log 7/2n）线。(3)我们给出了紧密的平均情况下（门和线）的复杂性计算PARITY与深度两个阈值电路的结果，答案原来是相同的深度两个多数电路。其关键是提出了一种分析线性阈值函数随机约束的新方法。我们的主要分析工具是加法组合学中的Littlewood-Offord引理。
In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. (1) We prove that for all ε ≪ √log(n)/n, the linear-time computable Andreev’s function cannot be computed on a (1/2+ε)-fraction of n-bit inputs by depth-two circuits of o(ε3 n3/2/log3 n) gates, nor can it be computed with o(ε3 n5/2/log7/2 n) wires. This establishes an average-case “size hierarchy” for threshold circuits, as Andreev’s function is computable by uniform depth-two circuits of o(n3) linear threshold gates, and by uniform depth-three circuits of O(n) majority gates. (2) We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two threshold circuits of o(n3/2/log3 n) gates, nor with o(n5/2/log7/2n) wires. (3) We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new method for analyzing random restrictions to linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.