Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. Kane University of California, San Diego Ryan Williams Stanford University Supported by an Alfred P. Sloan Fellowship and NSF CCF-1212372. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF. Part of the work was performed while visiting the Simons Institute for the Theory of Computing, Berkeley, CA.
Abstract
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.
中文速览
对深度两层线性阈值电路（Linear Threshold Function, LTF）和深度三层多数门电路（Majority circuit）能计算哪些函数、需要多大规模，理论界此前几十年几乎毫无进展。本文借助加法组合学中的 Littlewood-Offord 引理，设计了一种针对线性阈值函数的随机限制（random restriction）引理，再结合多路选择器构造与小偏集（small-biased set）技术，对两个显式可计算函数——Andreev 函数和新构造的函数 $B_n$——分别证明了深度两层 LTF 电路需要超线性数量的门（$\tilde{\Omega}(n^{3/2})$）和超二次数量的连线（$\tilde{\Omega}(n^{5/2})$），同时给出了用 PARITY 函数逼近深度两层阈值电路复杂度的精确上下界。这些结果是该模型迄今最强的下界，建立了低深度阈值电路的平均情况复杂度层级，为最终分离 $\mathsf{NC}^1$ 与 $\mathsf{TC}^0$ 这一长期开放问题迈出了关键一步。
原文 arXiv:1511.07860;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1511.07860v1