{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:50Z","timestamp":1781078270152,"version":"3.54.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,5,24]],"date-time":"2018-05-24T00:00:00Z","timestamp":1527120000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00037-018-0168-4","type":"journal-article","created":{"date-parts":[[2018,5,24]],"date-time":"2018-05-24T05:05:56Z","timestamp":1527138356000},"page":"671-716","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["An adaptivity hierarchy theorem for property testing"],"prefix":"10.1007","volume":"27","author":[{"given":"Cl\u00e9ment L.","family":"Canonne","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom","family":"Gur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,5,24]]},"reference":[{"key":"168_CR1","unstructured":"Scott Aaronson & Avi Wigderson (2008). Algebrization: a new barrier in complexity theory. In Proceedings of STOC, 731\u2013740. \n                    http:\/\/doi.acm.org\/10.1145\/1374376.1374481"},{"issue":"4","key":"168_CR2","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s004930070001","volume":"20","author":"Noga Alon","year":"2000","unstructured":"Alon, Noga, Fischer, Eldar, Krivelevich, Michael, Szegedy, Mario: Efficient Testing of Large Graphs. Combinatorica 20(4), 451\u2013476 (2000). \n                    https:\/\/doi.org\/10.1007\/s004930070001","journal-title":"Combinatorica"},{"issue":"4","key":"168_CR3","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"Eli Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, Eli, Goldreich, Oded, Harsha, Prahladh, Sudan, Madhu, Vadhan, Salil P.: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing 36(4), 889\u2013974 (2006). \n                    https:\/\/doi.org\/10.1137\/S0097539705446810","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"168_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"Eli Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, Eli, Harsha, Prahladh, Raskhodnikova, Sofya: Some 3CNF Properties Are Hard to Test. SIAM J. Comput. 35(1), 1\u201321 (2005). \n                    https:\/\/doi.org\/10.1137\/S0097539704445445","journal-title":"SIAM J. Comput."},{"key":"168_CR5","unstructured":"Arnab Bhattacharyya & Yuichi Yoshida (2017). Property Testing. Forthcoming. \n                    https:\/\/propertytestingbook.wordpress.com\/"},{"key":"168_CR6","doi-asserted-by":"crossref","unstructured":"Abhishek Bhrushundi, Sourav Chakraborty & Raghav Kulkarni (2014). Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees. In CSR, volume 8476 of Lecture Notes in Computer Science, 97\u2013110. Springer","DOI":"10.1007\/978-3-319-06686-8_8"},{"key":"168_CR7","doi-asserted-by":"crossref","unstructured":"Eric Blais (2008). Improved bounds for testing juntas. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 317\u2013330. Springer","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"168_CR8","doi-asserted-by":"crossref","unstructured":"Eric Blais (2009). Testing juntas nearly optimally. In Proceedings of STOC, 151\u2013158. ACM","DOI":"10.1145\/1536414.1536437"},{"issue":"2","key":"168_CR9","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00037-012-0040-x","volume":"21","author":"Eric Blais","year":"2012","unstructured":"Blais, Eric, Brody, Joshua, Matulef, Kevin: Property Testing Lower Bounds via Communication Complexity. Computational Complexity 21(2), 311\u2013358 (2012). \n                    https:\/\/doi.org\/10.1007\/s00037-012-0040-x","journal-title":"Computational Complexity"},{"key":"168_CR10","unstructured":"Eric Blais & Daniel M. Kane (2012). Tight Bounds for Testing \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -Linearity. In Proceedings of APPROX-RANDOM, volume 7408 of Lecture Notes in Computer Science, 435\u2013446. Springer"},{"issue":"3","key":"168_CR11","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"Manuel Blum","year":"1993","unstructured":"Blum, Manuel, Luby, Michael, Rubinfeld, Ronitt: Self-Testing\/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"168_CR12","doi-asserted-by":"crossref","unstructured":"Joshua Brody, Kevin Matulef & Chenggang Wu (2011). Lower Bounds for Testing Computability by Small Width OBDDs. In TAMC, volume 6648 of Lecture Notes in Computer Science, 320\u2013331. Springer","DOI":"10.1007\/978-3-642-20877-5_32"},{"key":"168_CR13","first-page":"2013","volume-title":"The non-adaptive query complexity of testing $$k$$ k","author":"Harry Buhrman","year":"2013","unstructured":"Buhrman, Harry, Garc\u00eda-Soriano, David, Matsliah, Arie, de Wolf, Ronald: The non-adaptive query complexity of testing \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -parities, p. 2013. Chicago J. Theor. Comput, Sci (2013)"},{"issue":"1","key":"168_CR14","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"Harry Buhrman & Ronald de Wolf","year":"2002","unstructured":"Harry Buhrman & Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002). \n                    https:\/\/doi.org\/10.1016\/S0304-3975(01)00144-X","journal-title":"Theor. Comput. Sci."},{"key":"168_CR15","unstructured":"Cl\u00e9ment L. Canonne (2015). A Survey on Distribution Testing: your Data is Big. But is it Blue? Electronic Colloquium on Computational Complexity (ECCC) 22, 63"},{"key":"168_CR16","doi-asserted-by":"publisher","unstructured":"Cl\u00e9ment L. Canonne & Tom Gur (2017). An Adaptivity Hierarchy Theorem for Property Testing. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, Ryan O'Donnell, editor, volume 79 of LIPIcs, 27:1\u201327:25. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. \n                    https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.27","DOI":"10.4230\/LIPIcs.CCC.2017.27"},{"key":"168_CR17","unstructured":"Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten & Jinyu Xie (2017). Settling the query complexity of non-adaptive junta testing. In Computational Complexity Conference (CCC), volume 79 of LIPIcs, 26:1\u201326:19. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik"},{"key":"168_CR18","unstructured":"Dingzhu Du & Frank K. Hwang (2000). Combinatorial Group Testing and Its Applications. Applied Mathematics. World Scientific. ISBN 9789810241070. \n                    https:\/\/books.google.com\/books?id=KW5-CyUUOggC"},{"key":"168_CR19","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (editor) (2010). 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. ISBN 978-3-642-16366-1. \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-16367-8","DOI":"10.1007\/978-3-642-16367-8"},{"key":"168_CR20","first-page":"73","volume":"20","author":"Oded Goldreich","year":"2013","unstructured":"Goldreich, Oded: 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)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"168_CR21","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2017). Introduction to Property Testing. Forthcoming. \n                    http:\/\/www.wisdom.weizmann.ac.il\/~oded\/pt-intro.html","DOI":"10.1017\/9781108135252"},{"issue":"4","key":"168_CR22","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"Oded Goldreich","year":"1998","unstructured":"Goldreich, Oded, Goldwasser, Shafi, Ron, Dana: Property Testing and Its Connection to Learning and Approximation. Journal of the ACM 45(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"key":"168_CR23","unstructured":"Oded Goldreich, Tom Gur & Ilan Komargodski (2015). Strong Locally Testable Codes with Relaxed Local Decoders. In Conference on Computational Complexity, volume 33 of LIPIcs, 1\u201341. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik"},{"key":"168_CR24","first-page":"20","volume":"7","author":"Oded Goldreich & Dana Ron","year":"2000","unstructured":"Oded Goldreich & Dana Ron: On Testing Expansion in Bounded-Degree Graphs. Electronic Colloquium on Computational Complexity (ECCC) 7, 20 (2000)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"2","key":"168_CR25","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/090749621","volume":"40","author":"Oded Goldreich & Dana Ron","year":"2011","unstructured":"Oded Goldreich & Dana Ron: Algorithmic Aspects of Property Testing in the Dense Graphs Model. SIAM J. Comput. 40(2), 376\u2013445 (2011). \n                    https:\/\/doi.org\/10.1137\/090749621","journal-title":"SIAM J. Comput."},{"issue":"1","key":"168_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/rsa.10078","volume":"23","author":"Oded Goldreich & Luca Trevisan","year":"2003","unstructured":"Oded Goldreich & Luca Trevisan: Three theorems regarding testing graph properties. Random Struct. Algorithms 23(1), 23\u201357 (2003). \n                    https:\/\/doi.org\/10.1002\/rsa.10078","journal-title":"Random Struct. Algorithms"},{"key":"168_CR27","unstructured":"Tom Gur & Ron D. Rothblum (2017). A Hierarchy Theorem for Interactive Proofs of Proximity. In 8th Innovations in Theoretical Computer Science (ITCS), volume 67 of LIPIcs, 39:1\u201339:43. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik"},{"key":"168_CR28","doi-asserted-by":"publisher","unstructured":"Indyk, Piotr, Price, Eric, Woodruff, David P.: On the Power of Adaptivity in Sparse Recovery. In Proceedings of FOCS 285\u2013294, (2011). \n                    https:\/\/doi.org\/10.1109\/FOCS.2011.83","DOI":"10.1109\/FOCS.2011.83"},{"key":"168_CR29","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press. ISBN 978-0-521-56067-2","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"168_CR30","unstructured":"Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld & Rocco A. Servedio (2009). Testing \n                    \n                      \n                    \n                    $$\\pm $$\n                    \n                      \n                        \u00b1\n                      \n                    \n                  1-weight halfspace. In Proceedings of APPROX-RANDOM, volume 5687 of Lecture Notes in Computer Science, 646\u2013657. Springer"},{"issue":"1","key":"168_CR31","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"Noam Nisan","year":"1993","unstructured":"Noam Nisan & Avi Wigderson (1993). Rounds in Communication Complexity Revisited. SIAM Journal on Computing 22(1), 211\u2013219. ISSN 0097-5397. \n                    http:\/\/dx.doi.org\/10.1137\/0222016","journal-title":"SIAM Journal on Computing"},{"key":"168_CR32","unstructured":"Christos H. Papadimitriou & Michael Sipser (1982). Communication Complexity. In Proceedings of STOC, Proceedings of STOC, 196\u2013200. ACM, New York, NY, USA. ISBN 0-89791-070-2. \n                    http:\/\/doi.acm.org\/10.1145\/800070.802192"},{"key":"168_CR33","unstructured":"Sofya Raskhodnikova & Adam D. Smith (2006). A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electronic Colloquium on Computational Complexity (ECCC) 13(089). \n                    http:\/\/eccc.hpi-web.de\/eccc-reports\/2006\/TR06-089\/index.html"},{"issue":"3","key":"168_CR34","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1561\/2200000004","volume":"1","author":"Dana Ron","year":"2008","unstructured":"Ron, Dana: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3), 307\u2013402 (2008). \n                    https:\/\/doi.org\/10.1561\/2200000004","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"2","key":"168_CR35","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"Dana Ron","year":"2009","unstructured":"Ron, Dana: Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science 5(2), 73\u2013205 (2009). \n                    https:\/\/doi.org\/10.1561\/0400000029","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"168_CR36","unstructured":"Dana Ron & Rocco A. Servedio (2013). Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. In Proceedings of SODA, 1319\u20131336. SIAM"},{"key":"168_CR37","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2011.11.007","volume":"420","author":"Dana Ron & Gilad Tsur","year":"2012","unstructured":"Dana Ron & Gilad Tsur: Testing computability by width-two OBDDs. Theor. Comput. Sci. 420, 64\u201379 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"168_CR38","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"Ronitt Rubinfeld & Madhu Sudan","year":"1996","unstructured":"Ronitt Rubinfeld & Madhu Sudan: Robust Characterization of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"168_CR39","unstructured":"Mert Sa\u011flam & G\u00e1bor Tardos (2013). On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems. In Proceedings of FOCS, 678\u2013687. IEEE Computer Society"},{"key":"168_CR40","unstructured":"Rocco A. Servedio, Li-Yang Tan & John Wright (2015). Adaptivity Helps for Testing Juntas. In Conference on Computational Complexity, volume 33 of LIPIcs, 264\u2013279. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik"},{"key":"168_CR41","first-page":"115","volume":"21","author":"Roei Tell","year":"2014","unstructured":"Tell, Roei: Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees. Electronic Colloquium on Computational Complexity (ECCC) 21, 115 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-018-0168-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0168-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0168-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T19:11:41Z","timestamp":1558638701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-018-0168-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,24]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["168"],"URL":"https:\/\/doi.org\/10.1007\/s00037-018-0168-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,24]]},"assertion":[{"value":"15 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}