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

文章基本信息

  • 标题:The non-adaptive query complexity of testing k-parities
  • 本地全文:下载
  • 作者:Harry Buhrman ; David García-Soriano ; Arie Matsliah
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2013
  • 卷号:2013
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    We prove tight bounds of $\Theta(k \log k)$ queries for non-adaptively testing whether a function $f: \{ 0,1 \}^n \to \{ 0,1 \}$ is a $k$-parity or far from any $k$-parity. The lower bound combines a recent method of Blais, Brody and Matulef to get lower bounds for testing from communication complexity with an $\Omega(k\log k)$ lower bound for the one-way communication complexity of $k$-disjointness.

国家哲学社会科学文献中心版权所有