An Adaptivity Hierarchy Theorem for Property Testing

Authors Clément L. Canonne, Tom Gur



PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.27.pdf
  • Filesize: 0.65 MB
  • 25 pages

Document Identifiers

Author Details

Clément L. Canonne
Tom Gur

Cite AsGet BibTex

Clément L. Canonne and Tom Gur. An Adaptivity Hierarchy Theorem for Property Testing. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 27:1-27:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CCC.2017.27

Abstract

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers received to prior queries, and their non-adaptive counterparts, in which all queries are independent of answers obtained from previous queries. In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of "rounds of adaptivity" it uses. More accurately, we say that a tester is k-(round) adaptive if it makes queries in k+1 rounds, where the queries in the i'th round may depend on the answers obtained in the previous i-1 rounds. Then, we ask the following question: Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity? We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every n in N and 0 <= k <= n^{0.99} there exists a property Pi_{n,k} of functions for which (1) there exists a k-adaptive tester for Pi_{n,k} with query complexity tilde O(k), yet (2) any (k-1)-adaptive tester for Pi_{n,k} must make Omega(n) queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.
Keywords
  • Property Testing
  • Coding Theory
  • Hierarchy Theorems

Metrics

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

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. In Proceedings of STOC, pages 731-740, 2008. URL: http://dx.doi.org/10.1145/1374376.1374481.
  2. Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451-476, 2000. URL: http://dx.doi.org/10.1007/s004930070001.
  3. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing, 36(4):889-974, 2006. URL: http://dx.doi.org/10.1137/S0097539705446810.
  4. Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. Some 3CNF properties are hard to test. SIAM J. Comput., 35(1):1-21, 2005. URL: http://dx.doi.org/10.1137/S0097539704445445.
  5. Arnab Bhattacharyya and Yuichi Yoshida. Property Testing. Forthcoming, 2017. URL: https://propertytestingbook.wordpress.com/.
  6. Abhishek Bhrushundi, Sourav Chakraborty, and Raghav Kulkarni. Property testing bounds for linear and quadratic functions via parity decision trees. In CSR, volume 8476 of Lecture Notes in Computer Science, pages 97-110. Springer, 2014. Google Scholar
  7. Eric Blais. Improved bounds for testing juntas. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 317-330. Springer, 2008. Google Scholar
  8. Eric Blais. Testing juntas nearly optimally. In Proceedings of STOC, pages 151-158. ACM, 2009. Google Scholar
  9. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. URL: http://dx.doi.org/10.1007/s00037-012-0040-x.
  10. Eric Blais and Daniel M. Kane. Tight bounds for testing k-linearity. In Proceedings of APPROX-RANDOM, volume 7408 of Lecture Notes in Computer Science, pages 435-446. Springer, 2012. Google Scholar
  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. Google Scholar
  12. Joshua Brody, Kevin Matulef, and Chenggang Wu. Lower bounds for testing computability by small width OBDDs. In TAMC, volume 6648 of Lecture Notes in Computer Science, pages 320-331. Springer, 2011. Google Scholar
  13. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00144-X.
  14. Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf. The non-adaptive query complexity of testing k-parities. Chicago J. Theor. Comput. Sci., 2013, 2013. Google Scholar
  15. Clément L. Canonne. A Survey on Distribution Testing: your data is Big. But is it Blue? Electronic Colloquium on Computational Complexity (ECCC), 22:63, April 2015. Google Scholar
  16. Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. In Computational Complexity Conference (CCC), 2017. To appear. Google Scholar
  17. Dingzhu Du and Frank K. Hwang. Combinatorial Group Testing and Its Applications. Applied Mathematics. World Scientific, 2000. URL: https://books.google.com/books?id=KW5-CyUUOggC, URL: http://dx.doi.org/10.1142/4252.
  18. Oded Goldreich, editor. Property Testing - Current Research and Surveys [outgrow of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010], volume 6390 of Lecture Notes in Computer Science. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-16367-8.
  19. Oded Goldreich. On the communication complexity methodology for proving lower bounds on the query complexity of property testing. Electronic Colloquium on Computational Complexity (ECCC), 20:73, 2013. Google Scholar
  20. Oded Goldreich. Introduction to Property Testing. Forthcoming, 2017. URL: http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html.
  21. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, July 1998. Google Scholar
  22. Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong locally testable codes with relaxed local decoders. In 30th Conference on Computational Complexity (CCC 2015), volume 33 of LIPIcs, pages 1-41. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.1.
  23. Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 7:20, 2000. Google Scholar
  24. Oded Goldreich and Dana Ron. Algorithmic aspects of property testing in the dense graphs model. SIAM J. Comput., 40(2):376-445, 2011. URL: http://dx.doi.org/10.1137/090749621.
  25. Oded Goldreich and Luca Trevisan. Three theorems regarding testing graph properties. Random Struct. Algorithms, 23(1):23-57, 2003. URL: http://dx.doi.org/10.1002/rsa.10078.
  26. Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. 2017. The 8th Innovations in Theoretical Computer Science (ITCS 2017) conference (to appear). Google Scholar
  27. Piotr Indyk, Eric Price, and David P. Woodruff. On the power of adaptivity in sparse recovery. In Proceedings of FOCS, pages 285-294, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.83.
  28. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing ±1-weight halfspace. In Proceedings of APPROX-RANDOM, volume 5687 of Lecture Notes in Computer Science, pages 646-657. Springer, 2009. Google Scholar
  29. Noam Nisan and Avi Wigderson. Rounds in communication complexity revisited. SIAM Journal on Computing, 22(1):211-219, February 1993. URL: http://dx.doi.org/10.1137/0222016.
  30. Christos H. Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of STOC, Proceedings of STOC, pages 196-200, New York, NY, USA, 1982. ACM. URL: http://dx.doi.org/10.1145/800070.802192.
  31. Sofya Raskhodnikova and Adam D. Smith. A note on adaptivity in testing properties of bounded degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 13(089), 2006. URL: http://eccc.hpi-web.de/eccc-reports/2006/TR06-089/index.html.
  32. Dana Ron. Property testing: A learning theory perspective. Foundations and Trends in Machine Learning, 1(3):307-402, 2008. URL: http://dx.doi.org/10.1561/2200000004.
  33. Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5(2):73-205, 2009. URL: http://dx.doi.org/10.1561/0400000029.
  34. Dana Ron and Rocco A. Servedio. Exponentially improved algorithms and lower bounds for testing signed majorities. In Proceedings of SODA, pages 1319-1336. SIAM, 2013. Google Scholar
  35. Dana Ron and Gilad Tsur. Testing computability by width-two OBDDs. Theor. Comput. Sci., 420:64-79, 2012. Google Scholar
  36. Ronitt Rubinfeld and Madhu Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  37. Mert Sağlam and Gábor Tardos. On the communication complexity of sparse set disjointness and exists-equal problems. In Proceedings of FOCS, pages 678-687. IEEE Computer Society, 2013. Google Scholar
  38. Rocco A. Servedio, Li-Yang Tan, and John Wright. Adaptivity helps for testing juntas. In 30th Conference on Computational Complexity (CCC 2015), volume 33 of LIPIcs, pages 264-279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.264.
  39. Roei Tell. Deconstructions of reductions from communication complexity to property testing using generalized parity decision trees. Electronic Colloquium on Computational Complexity (ECCC), 21:115, 2014. 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