首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Sign rank vs Discrepancy
  • 本地全文:下载
  • 作者:Hamed Hatami ; Kaave Hosseini ; Shachar Lovett
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-15
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions. In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank is only 3 , and yet its discrepancy is 2 − ( n ) . We note that every matrix of sign-rank 2 has discrepancy n − O (1) . Our result in particular implies that there are Boolean functions with O (1) unbounded error randomized communication complexity while having ( n ) weakly unbounded error randomized communication complexity.

  • 关键词:Discrepancy ; sign rank ; Unbounded-error communication complexity ; weakly unbounded error communication complexity
国家哲学社会科学文献中心版权所有