Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
复制标题
AC0 阈值度和符号秩的近最优下界
DOI：
10.1145/3313276.3316408
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wu, Pei
中科院分区：
文献类型：
--
作者：
Sherstov, Alexander A.;Wu, Pei
布尔函数f ∶{0，1}n→{0，1}的阈值次数是表示f符号的真实的多项式p的最小次数：sgnp（x）=（−1）f（x）。一个相关的概念是符号秩，对于布尔矩阵F =[Fij]定义为真实的矩阵M的最小秩，其中sgnMij =（−1）Fij。确定恒定深度电路（AC 0）可达到的最大阈值度和符号秩是一个著名的、被广泛研究的公开问题，具有复杂性理论和算法的应用.本文给出了这个问题的本质最优解.对于任意n>0，我们构造了一个具有阈值度Ω（n1− n）和符号秩exp（Ω（n1− n））的AC 0电路不变量，分别改进了以前的Ω（n）和exp（Ω（n））的最佳下界。我们的结果subsumeallprevious下限的阈值程度和符号秩的AC 0电路的任何给定的深度，从深度4严格的改进。作为一个推论，我们还获得了接近最优的界限的差异，阈值权重，和阈值密度的AC 0，严格包含以前的工作，这些数量。我们的工作给出了一些最强的下限到目前为止的通信复杂性AC 0。
Thethreshold degreeof a Boolean functionf∶{0,1}n→{0,1} is the minimum degree of a real polynomialpthat representsfin sign:sgnp(x)=(−1)f(x). A related notion issign-rank, defined for a Boolean matrixF=[Fij] as the minimum rank of a real matrixMwithsgnMij=(−1)Fij. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC0) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications.We give an essentially optimal solution to this problem. For any є>0, we construct an AC0circuit innvariables that has threshold degree Ω(n1−є) and sign-rank exp(Ω(n1−є)), improving on the previous best lower bounds of Ω(√n) and exp(Ω(√n)), respectively. Our results subsumeallprevious lower bounds on the threshold degree and sign-rank of AC0circuits of any given depth, with a strict improvement starting at depth 4. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of AC0, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC0.