2026-07-22T07:05:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7528 2024-03-06T10:40:13Z ddc:004 open_access

Settling the Query Complexity of Non-Adaptive Junta Testing Chen, Xi Servedio, Rocco A. Tan, Li-Yang Waingarten, Erik Xie, Jinyu property testing juntas query complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Rocco A. Servedio and Li-Yang Tan and Erik Waingarten and Jinyu Xie 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.26 urn:nbn:de:0030-drops-75283 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.26 eng https://creativecommons.org/licenses/by/3.0/legalcode