文章基本信息

标题：Settling the Query Complexity of Non-Adaptive Junta Testing
本地全文：下载
作者：Xi Chen ; Rocco A. Servedio ; Li-Yang Tan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：79
页码：26:1-26:19
DOI：10.4230/LIPIcs.CCC.2017.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f is a k-junta or epsilon-far from every k-junta must make ~Omega(k^{3/2}/ epsilon) many queries for a wide range of parameters k and epsilon. 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})/epsilon queries. Combined with the adaptive tester of [Blais09] which makes O(k log k + k / epsilon) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.
关键词：property testing; juntas; query complexity