Document Open Access Logo

Settling the Query Complexity of Non-Adaptive Junta Testing

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

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.26.pdf
  • Filesize: 0.69 MB
  • 19 pages

Document Identifiers

Author Details

Xi Chen
Rocco A. Servedio
Li-Yang Tan
Erik Waingarten
Jinyu Xie

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.CCC.2017.26

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.
Keywords
  • property testing
  • juntas
  • query complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. José A Adell and Pedro Jodrá. Exact kolmogorov and total variation distances between some familiar discrete distributions. Journal of Inequalities and Applications, 2006(1):1-8, 2006. Google Scholar
  2. N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing Reed-Muller Codes. IEEE Transactions on Information Theory, 51(11):4032-4039, 2005. Google Scholar
  3. Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, and Sofya Raskhodnikova. Testing unateness of real-valued functions. CoRR, abs/1608.07652, 2016. Google Scholar
  4. A. Belovs and E. Blais. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th ACM Symposium on Theory of Computing, pages 1021-1032, 2016. Google Scholar
  5. Arthur J. Bernstein. Maximally connected arrays on the n-cube. SIAM J. Appl. Math., 15(6):1485-1489, 1967. Google Scholar
  6. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pages 488-497, 2010. Google Scholar
  7. Eric Blais. Improved bounds for testing juntas. In Proc. RANDOM, pages 317-330, 2008. Google Scholar
  8. Eric Blais. Testing juntas nearly optimally. In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), pages 151-158, 2009. URL: http://dx.doi.org/10.1145/1536414.1536437.
  9. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. In CCC, pages 210-220, 2011. Google Scholar
  10. Eric Blais and Daniel M. Kane. Tight bounds for testing k-linearity. In RANDOM, pages 435-446, 2012. Google Scholar
  11. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47:549-595, 1993. Earlier version in STOC'90. Google Scholar
  12. Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf. The non-adaptive query complexity of testing k-parities. Chicago Journal of Theoretical Computer Science, 2013, 2013. Google Scholar
  13. Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 411-418, 2013. Google Scholar
  14. Deeparnab Chakrabarty and C. Seshadhri. A Õ(n) non-adaptive tester for unateness. CoRR, abs/1608.06980, 2016. Google Scholar
  15. Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. In Proceedings of the 47th ACM Symposium on Theory of Computing, pages 519-528, 2015. Google Scholar
  16. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for testing monotonicity. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science, pages 286-295, 2014. Google Scholar
  17. H. Chockler and D. Gutfreund. A lower bound for testing juntas. Information Processing Letters, 90(6):301-305, 2004. Google Scholar
  18. I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, and A. Wan. Testing for concise representations. In Proc. 48th Ann. Symposium on Computer Science (FOCS), pages 549-558, 2007. Google Scholar
  19. E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky. Testing juntas. J. Computer &System Sciences, 68(4):753-787, 2004. Google Scholar
  20. E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky. Monotonicity testing over general poset domains. In Proc. 34th Annual ACM Symposium on the Theory of Computing, pages 474-483, 2002. Google Scholar
  21. Peter Frankl. On the trace of finite sets. J. Comb. Theory, Ser. A, 34(1):41-45, 1983. Google Scholar
  22. O. Goldreich, editor. Property Testing: Current Research and Surveys. Springer, 2010. LNCS 6390. Google Scholar
  23. O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. Combinatorica, 20(3):301-337, 2000. Google Scholar
  24. P. Gopalan, R. O'Donnell, R. Servedio, A. Shpilka, and K. Wimmer. Testing Fourier dimensionality and sparsity. SIAM J. on Computing, 40(4):1075-1100, 2011. Google Scholar
  25. Larry H. Harper. Optimal assignments of numbers to vertices. SIAM J. Appl. Math., 12(1):131-135, 1964. Google Scholar
  26. Sergiu Hart. A note on the edges of the n-cube. Disc. Math., 14:157-163, 1976. Google Scholar
  27. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric type theorems. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science, pages 52-58, 2015. Google Scholar
  28. Subhash Khot and Igor Shinkar. An o(n) queries adaptive tester for unateness. In Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques, 2016. Google Scholar
  29. J. H. Lindsey. Assignment of numbers to vertices. Amer. Math. Monthly, 71:508-516, 1964. Google Scholar
  30. K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. Testing halfspaces. SIAM J. on Comput., 39(5):2004-2047, 2010. Google Scholar
  31. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing ±1-weight halfspace. In APPROX-RANDOM, pages 646-657, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03685-9_48.
  32. M. Parnas, D. Ron, and A. Samorodnitsky. Testing Basic Boolean Formulae. SIAM J. Disc. Math., 16:20-46, 2002. Google Scholar
  33. D. Ron. Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 1(3):307-402, 2008. Google Scholar
  34. D. Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5:73-205, 2010. Google Scholar
  35. D. Ron and R. Servedio. Exponentially improved algorithms and lower bounds for testing signed majorities. In SODA, pages 1319-1336, 2013. Google Scholar
  36. Dana Ron and Gilad Tsur. Testing computability by width-two obdds. Technical Report 11(041), ECCC, 2011. available at http://eccc.hpi-web.de/report 041/. Google Scholar
  37. B. Roos. Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion. Theory Probab. Appl., 45:328-344, 2000. Google Scholar
  38. Rocco Servedio, Li-Yang Tan, and John Wright. Adaptivity helps for testing juntas. In Proceedings of the 30th IEEE Conference on Computational Complexity, pages 264-279, 2015. volume 33 of LIPIcs. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact