{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:01:56Z","timestamp":1775282516024,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,5,30]],"date-time":"2012-05-30T00:00:00Z","timestamp":1338336000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00037-012-0040-x","type":"journal-article","created":{"date-parts":[[2012,5,29]],"date-time":"2012-05-29T05:40:40Z","timestamp":1338270040000},"page":"311-358","source":"Crossref","is-referenced-by-count":42,"title":["Property Testing Lower Bounds via Communication Complexity"],"prefix":"10.1007","volume":"21","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[]},{"given":"Joshua","family":"Brody","sequence":"additional","affiliation":[]},{"given":"Kevin","family":"Matulef","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,30]]},"reference":[{"key":"40_CR1","unstructured":"Noga Alon & Eric Blais (2010). Testing Boolean Function Isomorphism. In Proc. 14th International Workshop on Randomization and Approximation Techniques in Computer Science, 394\u2013405."},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar & D. Sivakumar (2002). An Information Statistics Approach to Data Stream and Communication Complexity. In Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, 209\u2013218.","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Tugkan Batu, Ronitt Rubinfeld & Patrick White (1999). Fast Approximate PCPs for Multidimensional Bin-Packing Problems. In Proc. 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, 245\u2013256.","DOI":"10.1007\/978-3-540-48413-4_25"},{"key":"40_CR4","unstructured":"Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova & David P. Woodruff (2009). Transitive-Closure Spanners of the Hypercube and the Hypergrid. Technical Report TR09-046, ECCC."},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Eric Blais (2008). Improved Bounds for Testing Juntas. In Proc. 12th International Workshop on Randomization and Approximation Techniques in Computer Science, 317\u2013330.","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Eric Blais (2009). Testing Juntas Nearly Optimally. In Proc. 41st Annual ACM Symposium on the Theory of Computing, 151\u2013158.","DOI":"10.1145\/1536414.1536437"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Eric Blais, Joshua Brody & Kevin Matulef (2011). Property Testing Lower Bounds via Communication Complexity. In Proc. 26th Annual IEEE Conference on Computational Complexity.","DOI":"10.1109\/CCC.2011.31"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Eric Blais, Joshua Brody & Kevin Matulef (2012). Erratum to Property Testing Lower Bounds via Communication Complexity.","DOI":"10.1109\/CCC.2011.31"},{"key":"40_CR9","unstructured":"Eric Blais & Daniel Kane (2011). Testing Properties of Linear Functions. Manuscript."},{"key":"40_CR10","doi-asserted-by":"crossref","unstructured":"Eric Blais & Ryan O\u2019Donnell (2010). Lower Bounds for Testing Function Isomorphism. In Proc. 25th Annual IEEE Conference on Computational Complexity, 235\u2013246.","DOI":"10.1109\/CCC.2010.30"},{"key":"40_CR11","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"Blum Manuel","year":"1993","unstructured":"Manuel Blum, Michael Luby & Ronitt Rubinfeld (1993). Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 549\u2013595. Earlier version in STOC\u201990.","journal-title":"J. Comput. Syst. Sci"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Jop Bri\u00ebt, Sourav Chakraborty, David Garc\u00eda Soriano & Arie Matsliah (2010). Monotonicity Testing and Shortest-Path Routing on the Cube. In Proc. 14th International Workshop on Randomization and Approximation Techniques in Computer Science.","DOI":"10.1007\/978-3-642-15369-3_35"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick & Ronald de Wolf (2010). Better Gap-Hamming Lower Bounds via Better Round Elimination. In Proc. 14th International Workshop on Randomization and Approximation Techniques in Computer Science.","DOI":"10.1007\/978-3-642-15369-3_36"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Joshua Brody, Kevin Matulef & Chenggang Wu (2011). Lower Bounds for Testing Computability by Small-Width Branching Programs. In Proc. 8th Annual Theory and Applications of Models of Computation.","DOI":"10.1007\/978-3-642-20877-5_32"},{"key":"40_CR15","unstructured":"Harry Buhrman, Richard Cleve & Avi Wigderson (1998). Quantum vs. classical communication and computation. In Proc. 30th Annual ACM Symposium on the Theory of Computing, 63\u201368."},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Amit Chakrabarti & Oded Regev (2011). An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. In Proc. 43rd Annual ACM Symposium on the Theory of Computing.","DOI":"10.1145\/1993636.1993644"},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Sourav Chakraborty, David Garc\u00eda Soriano & Arie Matsliah (2011a). Efficient Sample Extractors for Juntas with Applications. In Proc. 38th International Colloquium on Automata, Languages and Programming.","DOI":"10.1007\/978-3-642-22006-7_46"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Sourav Chakraborty, David Garc\u00eda Soriano & Arie Matsliah (2011b). Nearly tight bounds for testing function isomorphism. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms.","DOI":"10.1137\/1.9781611973082.130"},{"issue":"6","key":"40_CR19","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.ipl.2004.01.023","volume":"90","author":"Chockler Hana","year":"2004","unstructured":"Hana Chockler & Dan Gutfreund (2004). A lower bound for testing juntas. Information Processing Letters 90(6), 301\u2013305.","journal-title":"Information Processing Letters"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio & Andrew Wan (2007). Testing for Concise Representations. In Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, 549\u2013558.","DOI":"10.1109\/FOCS.2007.32"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron & Alex Samorodnitsky (1999). Improved testing algorithms for monotonicity. In Proc. 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, 97\u2013108.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"40_CR22","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"Ergun Funda","year":"2000","unstructured":"Funda Ergun, Sampath Kannan, Ravi Kumar, Ronitt Rubenfeld, Mahesh Viswanathan (2000) J. Comput. Syst. Sci. 717\u2013751","journal-title":"J. Comput. Syst. Sci."},{"key":"40_CR23","volume-title":"An introduction to probability theory and its applications, volume 2","author":"W. Feller","year":"1968","unstructured":"Feller W. (1968) An introduction to probability theory and its applications, volume 2. John Wiley, Sons"},{"key":"40_CR24","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"Fischer Eldar","year":"2004","unstructured":"Eldar Fischer, Guy Kindler, Dana Ron, Safra Shmuel , Samorodnitsky Alex (2004) Testing juntas. J. Comput. Syst. Sci. 68: 753\u2013787","journal-title":"J. Comput. Syst. Sci."},{"key":"40_CR25","doi-asserted-by":"crossref","unstructured":"Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld & Alex Samorodnitsky (2002). Monotonicity testing over general poset domains. In Proc. 34th Annual ACM Symposium on the Theory of Computing, 474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"40_CR26","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2010a). On Testing Computability by Small Width OBDDs. In Proc. 14th International Workshop on Randomization and Approximation Techniques in Computer Science, 574\u2013587.","DOI":"10.1007\/978-3-642-15369-3_43"},{"key":"40_CR27","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (editor) (2010b). Property Testing: Current Research and Surveys, volume 6390 of LNCS. Springer.","DOI":"10.1007\/978-3-642-16367-8"},{"issue":"3","key":"40_CR28","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"Goldreich Oded","year":"2000","unstructured":"Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky (2000) Testing monotonicity. Combinatorica 20(3): 301\u2013337","journal-title":"Combinatorica"},{"issue":"4","key":"40_CR29","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"Goldreich Oded","year":"1998","unstructured":"Oded Goldreich, Shafi Goldwasser, Dana Ron (1998) Property Testing and its Connection to Learning and Approximation. J. ACM 45(4): 653\u2013750","journal-title":"J. ACM"},{"key":"40_CR30","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad & Avi Wigderson (2007). The Randomized Communication Complexity of Set Disjointness. Theory of Computing 211\u2013219.","DOI":"10.4086\/toc.2007.v003a011"},{"key":"40_CR31","doi-asserted-by":"crossref","unstructured":"Piotr Indyk & David Woodruff (2003). Tight Lower Bounds for the Distinct Elements Problem. In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, 283\u2013289.","DOI":"10.1109\/SFCS.2003.1238202"},{"issue":"4","key":"40_CR32","first-page":"547","volume":"5","author":"Kalyanasundaram Bala","year":"1992","unstructured":"Bala Kalyanasundaram, Georg Schnitger (1992) The Probabilistic Communication Complexity of Set Intersection. SIAM J. Disc. Math. 5(4): 547\u2013557","journal-title":"Disc. Math."},{"key":"40_CR33","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","year":"1997","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication Complexity. Cambridge University Press, Cambridge."},{"key":"40_CR34","doi-asserted-by":"crossref","unstructured":"Kevin Matulef, Ryan O\u2019Donnell, Ronitt Rubinfeld & Rocco Servedio (2009). Testing {-1,1}-weight halfspaces. In Proc. 13th International Workshop on Randomization and Approximation Techniques in Computer Science.","DOI":"10.1007\/978-3-642-03685-9_48"},{"key":"40_CR35","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen, Noam Nisan, Shmuel Safra & Avi Wigderson (1995). On data structures and asymmetric communication complexity. In Proc. 27th Annual ACM Symposium on the Theory of Computing, 103\u2013111.","DOI":"10.1145\/225058.225093"},{"key":"40_CR36","doi-asserted-by":"crossref","unstructured":"Ryan O\u2019Donnell (2008). Some topics in analysis of Boolean function. In Proc. 40th Annual ACM Symposium on the Theory of Computing, 569\u2013578.","DOI":"10.1145\/1374376.1374458"},{"issue":"5","key":"40_CR37","doi-asserted-by":"crossref","first-page":"1158","DOI":"10.1137\/S0097539702414026","volume":"32","author":"Parnas Michal","year":"2003","unstructured":"Michal Parnas, Dana Ron, Ronitt Rubinfeld (2003) On Testing Convexity and Submodularity. SIAM J. Comput. 32(5): 1158\u20131184","journal-title":"SIAM J. Comput."},{"issue":"1","key":"40_CR38","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"Parnas Michal","year":"2002","unstructured":"Michal Parnas, Dana Ron, Alex Samorodnitsky (2002) Testing basic Boolean formulae. SIAM J. Disc. Math. 16(1): 20\u201346","journal-title":"SIAM J. Disc. Math."},{"key":"40_CR39","doi-asserted-by":"crossref","unstructured":"Alexander Razborov (1990). On the Distributional Complexity of Disjointness. In Proc. 17thInternational Colloquium on Automata, Languages and Programming, 249\u2013253.","DOI":"10.1007\/BFb0032036"},{"issue":"3","key":"40_CR40","first-page":"307","volume":"1","author":"Ron Dana","year":"2008","unstructured":"Dana Ron (2008) Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3): 307\u2013402","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"2","key":"40_CR41","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"Ron Dana","year":"2009","unstructured":"Dana Ron (2009) Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science 5(2): 73\u2013205","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"40_CR42","unstructured":"Dana Ron & Gilad Tsur (2009). Testing Computability by Width Two OBDDs. In Proc. 13th International Workshop on Randomization and Approximation Techniques in Computer Science, 686\u2013699."},{"key":"40_CR43","unstructured":"Dana Ron & Gilad Tsur (2011). On Approximating the Number of Relevant Variables in a Function. In Proc. 15thInternational Workshop on Randomization and Approximation Techniques in Computer Science, 676\u2013687."},{"key":"40_CR44","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"Rubinfeld Ronitt","year":"1996","unstructured":"Ronitt Rubinfeld, Madhu Sudan (1996) Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25: 252\u2013271","journal-title":"SIAM J. Comput."},{"key":"40_CR45","unstructured":"C. Seshadhri & Jan Vondr\u00e1k (2011). Is submodularity testable? In Proc. 2nd Innovations in Computer Science."},{"key":"40_CR46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.gs.2008.001","volume":"1","author":"Wolf Ronald de","year":"2008","unstructured":"Ronald de Wolf (2008) A Brief Introduction to Fourier Analysis on the Boolean Cube. Theory of Computing, Graduate Surveys 1: 1\u201320","journal-title":"Theory of Computing, Graduate Surveys"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0040-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0040-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0040-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T00:04:10Z","timestamp":1687478650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0040-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,30]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["40"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0040-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,30]]}}}