Document Open Access Logo

Almost Optimal Distribution-Free Junta Testing

Author Nader H. Bshouty

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.2.pdf
  • Filesize: 493 kB
  • 13 pages

Document Identifiers

Author Details

Nader H. Bshouty
  • Department of Computer Science, Technion, Haifa, Israel

Acknowledgements

We would like to thank Xi Chen for reading the early version of the paper and for verifying the correctness of the algorithm.

Cite As Get BibTex

Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.2

Abstract

We consider the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}^n. Chen, Liu, Servedio, Sheng and Xie [Zhengyang Liu et al., 2018] showed that the distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes O~(k^2)/epsilon queries. In this paper, we give a simple two-sided error adaptive algorithm that makes O~(k/epsilon) queries.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Probabilistic computation
Keywords
  • Distribution-free property testing
  • k-Junta

Metrics

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

Related Versions

References

  1. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Trans. Information Theory, 51(11):4032-4039, 2005. URL: https://doi.org/10.1109/TIT.2005.856958.
  2. Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, and Sofya Raskhodnikova. Testing Unateness of Real-Valued Functions. CoRR, abs/1608.07652, 2016. URL: http://arxiv.org/abs/1608.07652.
  3. Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 1021-1032, 2016. URL: https://doi.org/10.1145/2897518.2897567.
  4. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal Testing of Reed-Muller Codes. In Property Testing - Current Research and Surveys, pages 269-275. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16367-8_19.
  5. Eric Blais. Improved Bounds for Testing Juntas. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, pages 317-330, 2008. URL: https://doi.org/10.1007/978-3-540-85363-3_26.
  6. Eric Blais. Testing juntas nearly optimally. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 151-158, 2009. URL: https://doi.org/10.1145/1536414.1536437.
  7. Eric Blais, Joshua Brody, and Kevin Matulef. Property Testing Lower Bounds via Communication Complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 210-220, 2011. URL: https://doi.org/10.1109/CCC.2011.31.
  8. Eric Blais and Daniel M. Kane. Tight Bounds for Testing k-Linearity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 435-446, 2012. URL: https://doi.org/10.1007/978-3-642-32512-0_37.
  9. Avrim Blum. Learning a Function of r Relevant Variables. In Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, pages 731-733, 2003. URL: https://doi.org/10.1007/978-3-540-45167-9_54.
  10. Avrim Blum and Pat Langley. Selection of Relevant Features and Examples in Machine Learning. Artif. Intell., 97(1-2):245-271, 1997. URL: https://doi.org/10.1016/S0004-3702(97)00063-5.
  11. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
  12. Nader H. Bshouty and Areej Costa. Exact learning of juntas from membership queries. Theor. Comput. Sci., 742:82-97, 2018. URL: https://doi.org/10.1016/j.tcs.2017.12.032.
  13. Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 411-418, 2013. URL: https://doi.org/10.1145/2488608.2488660.
  14. Deeparnab Chakrabarty and C. Seshadhri. A Õ(n) Non-Adaptive Tester for Unateness. CoRR, abs/1608.06980, 2016. URL: http://arxiv.org/abs/1608.06980.
  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 Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 519-528, 2015. URL: https://doi.org/10.1145/2746539.2746570.
  16. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. CoRR, abs/1412.5655, 2014. URL: http://arxiv.org/abs/1412.5655.
  17. 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, July 6-9, 2017, Riga, Latvia, pages 26:1-26:19, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.26.
  18. Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 523-536, 2017. URL: https://doi.org/10.1145/3055399.3055461.
  19. Xi Chen, Erik Waingarten, and Jinyu Xie. Boolean Unateness Testing with Õ(n^3/4) Adaptive Queries. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 868-879, 2017. URL: https://doi.org/10.1109/FOCS.2017.85.
  20. Xi Chen and Jinyu Xie. Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 54-71, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch5.
  21. Hana Chockler and Dan Gutfreund. A lower bound for testing juntas. Inf. Process. Lett., 90(6):301-305, 2004. URL: https://doi.org/10.1016/j.ipl.2004.01.023.
  22. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. Testing for Concise Representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 549-558, 2007. URL: https://doi.org/10.1109/FOCS.2007.32.
  23. Elya Dolev and Dana Ron. Distribution-Free Testing for Monomials with a Sublinear Number of Queries. Theory of Computing, 7(1):155-176, 2011. URL: https://doi.org/10.4086/toc.2011.v007a011.
  24. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 474-483, 2002. URL: https://doi.org/10.1145/509907.509977.
  25. Dana Glasner and Rocco A. Servedio. Distribution-Free Testing Lower Bound for Basic Boolean Functions. Theory of Computing, 5(1):191-216, 2009. URL: https://doi.org/10.4086/toc.2009.v005a010.
  26. Oded Goldreich, editor. Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16367-8.
  27. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing Monotonicity. Combinatorica, 20(3):301-337, 2000. URL: https://doi.org/10.1007/s004930070011.
  28. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property Testing and its Connection to Learning and Approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  29. Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing Fourier Dimensionality and Sparsity. SIAM J. Comput., 40(4):1075-1100, 2011. URL: https://doi.org/10.1137/100785429.
  30. David Guijarro, Jun Tarui, and Tatsuie Tsukiji. Finding Relevant Variables in PAC Model with Membership Queries. In Algorithmic Learning Theory, 10th International Conference, ALT '99, Tokyo, Japan, December 6-8, 1999, Proceedings, page 313, 1999. URL: https://doi.org/10.1007/3-540-46769-6_26.
  31. Shirley Halevy and Eyal Kushilevitz. Distribution-Free Property-Testing. SIAM J. Comput., 37(4):1107-1138, 2007. URL: https://doi.org/10.1137/050645804.
  32. Subhash Khot, Dor Minzer, and Muli Safra. On Monotonicity Testing and Boolean Isoperimetric Type Theorems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 52-58, 2015. URL: https://doi.org/10.1109/FOCS.2015.13.
  33. Subhash Khot and Igor Shinkar. An Õ(n) Queries Adaptive Tester for Unateness. CoRR, abs/1608.02451, 2016. URL: http://arxiv.org/abs/1608.02451.
  34. Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, and Nisheeth K. Vishnoi. On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pages 112-119, 2005. URL: https://doi.org/10.1109/CCC.2005.19.
  35. Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie. Distribution-free junta testing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 749-759, 2018. URL: https://doi.org/10.1145/3188745.3188842.
  36. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing ±1-weight halfspace. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, pages 646-657, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_48.
  37. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing Halfspaces. SIAM J. Comput., 39(5):2004-2047, 2010. URL: https://doi.org/10.1137/070707890.
  38. Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning functions of k relevant variables. J. Comput. Syst. Sci., 69(3):421-434, 2004. URL: https://doi.org/10.1016/j.jcss.2004.04.002.
  39. Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing Basic Boolean Formulae. SIAM J. Discrete Math., 16(1):20-46, 2002. URL: http://epubs.siam.org/sam-bin/dbq/article/40744.
  40. Dana Ron. Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 1(3):307-402, 2008. URL: https://doi.org/10.1561/2200000004.
  41. Dana Ron. Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science, 5(2):73-205, 2009. URL: https://doi.org/10.1561/0400000029.
  42. Ronitt Rubinfeld and Madhu Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput., 25(2):252-271, 1996. URL: https://doi.org/10.1137/S0097539793255151.
  43. Mert Saglam. Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 967-978, 2018. URL: https://doi.org/10.1109/FOCS.2018.00095.
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 About DROPS Imprint Privacy Contact