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

文章基本信息

  • 标题:Settling the query complexity of non-adaptive junta testing
  • 本地全文:下载
  • 作者:Xi Chen ; Rocco Servedio ; Li-Yang Tan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f : 0 1 n 0 1 is a k -junta or -far from every k -junta must make ( k 3 2 ) many queries for a wide range of parameters k and . Our result dramatically improves previous lower bounds from [BGSMdW13, STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes O ( k 3 2 ) queries. Combined with the adaptive tester of [Blais09] which makes O ( k log k + k ) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

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