首页    期刊浏览 2024年11月27日 星期三
登录注册

文章基本信息

  • 标题:Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
  • 本地全文:下载
  • 作者:Alexander A. Sherstov ; Pei Wu
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-99
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The threshold degree of a Boolean function f : 0 1 n 0 1 is the minimum degree of a real polynomial p that represents f in sign: sgn p ( x ) = ( − 1 ) f ( x ) A related notion is sign-rank, defined for a Boolean matrix F = [ F i j ] as the minimum rank of a real matrix M with sgn M i j = ( − 1 ) F i j . Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits ( AC 0 ) 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,"> 0 we construct an AC 0 circuit in n variables that has threshold degree ( n 1 − ) and sign-rank exp ( ( n 1 − )) improving on the previous best lower bounds of ( n ) and exp ( ( n )) , respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of AC 0 circuits 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 AC 0 , strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC 0 .

  • 关键词:AC^0 ; Communication complexity ; constant-depth circuits ; sign-representation by polynomials ; threshold degree ; Unbounded-error communication
国家哲学社会科学文献中心版权所有