DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2017.26

Settling the Query Complexity of Non-Adaptive Junta Testing

Authors: Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract

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.

Cite as

Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the Query Complexity of Non-Adaptive Junta Testing. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CCC.2017.26,
  author =	{Chen, Xi and Servedio, Rocco A. and Tan, Li-Yang and Waingarten, Erik and Xie, Jinyu},
  title =	{{Settling the Query Complexity of Non-Adaptive Junta Testing}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.26},
  URN =		{urn:nbn:de:0030-drops-75283},
  doi =		{10.4230/LIPIcs.CCC.2017.26},
  annote =	{Keywords: property testing, juntas, query complexity}
}

Search Results

Documents authored by Xie, Jinyu

Settling the Query Complexity of Non-Adaptive Junta Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message