Document Open Access Logo

Almost Optimal Testers for Concise Representations

Author Nader H. Bshouty

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2020.5.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Probabilistic computation
Keywords
  • Property Testing
  • Boolean function
  • Junta

Metrics

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

Abstract

We give improved and almost optimal testers for several classes of Boolean functions on n variables that have concise representation in the uniform and distribution-free model. Classes, such as k-Junta, k-Linear, s-Term DNF, s-Term Monotone DNF, r-DNF, Decision List, r-Decision List, size-s Decision Tree, size-s Boolean Formula, size-s Branching Program, s-Sparse Polynomial over the binary field and functions with Fourier Degree at most d.
The approach is new and combines ideas from Diakonikolas et al. [Ilias Diakonikolas et al., 2007], Bshouty [Nader H. Bshouty, 2018], Goldreich et al. [Oded Goldreich et al., 1998], and learning theory. The method can be extended to several other classes of functions over any domain that can be approximated by functions with a small number of relevant variables.

Cite As Get BibTex

Nader H. Bshouty. Almost Optimal Testers for Concise Representations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.5

Author Details

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

Acknowledgements

I am extremely grateful to Oded Goldreich for very helpful discussions and comments and for allowing me to include his overview of the first tester in the paper (Section 2). I am also grateful to the reviewers of the earlier version of the manuscript for their helpful comments.

References

  1. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing low-degree polynomials over GF(2). In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003, Proceedings, pages 188-199, 2003. URL: https://doi.org/10.1007/978-3-540-45198-3_17.
  2. 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.
  3. Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1987. Google Scholar
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. Nader H. Bshouty. Almost optimal distribution-free junta testing. CoRR, abs/1901.00717, 2018. Google Scholar
  14. 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.
  15. 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.
  16. Deeparnab Chakrabarty and C. Seshadhri. A Õ(n) non-adaptive tester for unateness. CoRR, abs/1608.06980, 2016. URL: http://arxiv.org/abs/1608.06980.
  17. Sourav Chakraborty, David García-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 545-556, 2011. URL: https://doi.org/10.1007/978-3-642-22006-7_46.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. Peter Damaschke. Adaptive versus nonadaptive attribute-efficient learning. Machine Learning, 41(2):197-215, 2000. URL: https://doi.org/10.1023/A:1007616604496.
  24. 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.
  25. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, and Andrew Wan. Efficiently testing sparse GF(2) polynomials. Algorithmica, 61(3):580-605, 2011. URL: https://doi.org/10.1007/s00453-010-9426-9.
  26. 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.
  27. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 103-112, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181887.
  28. 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.
  29. 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.
  30. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  31. 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.
  32. 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.
  33. 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.
  34. 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.
  35. Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM J. Comput., 37(4):1107-1138, 2007. URL: https://doi.org/10.1137/050645804.
  36. 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.
  37. Subhash Khot and Igor Shinkar. An Õ(n) queries adaptive tester for unateness. CoRR, abs/1608.02451, 2016. URL: http://arxiv.org/abs/1608.02451.
  38. 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.
  39. 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.
  40. 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.
  41. 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.
  42. 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.
  43. 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.
  44. 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.
  45. 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.
  46. 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.
  47. 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.
  48. Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, 1984. URL: https://doi.org/10.1145/1968.1972.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact