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

文章基本信息

  • 标题:A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
  • 本地全文:下载
  • 作者:Roksana Baleshzar ; Deeparnab Chakrabarty ; Ramesh Krishnan S. Pallavoor
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    A Boolean function f : 0 1 d 0 1 is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make ( d log d ) queries. This result improves upon the ( d log 2 d ) lower bound for the same class of testers due to Chen et al. (STOC, 2017).

  • 关键词:testing unateness
国家哲学社会科学文献中心版权所有