{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:18:39Z","timestamp":1758824319764,"version":"3.40.5"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,6]],"date-time":"2014-11-06T00:00:00Z","timestamp":1415232000000},"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":[[2015,3]]},"DOI":"10.1007\/s00037-014-0092-1","type":"journal-article","created":{"date-parts":[[2014,11,5]],"date-time":"2014-11-05T09:04:33Z","timestamp":1415178273000},"page":"65-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Lower bounds for testing triangle-freeness in Boolean functions"],"prefix":"10.1007","volume":"24","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,6]]},"reference":[{"issue":"3-4","key":"92_CR1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.10056","volume":"21","author":"Alon Noga","year":"2002","unstructured":"Noga Alon (2002) Testing subgraphs in large graphs. Random Structures and Algorithms 21(3-4): 359\u2013370 ISSN 1042-9832.","journal-title":"Random Structures and Algorithms"},{"issue":"6","key":"92_CR2","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s004930070001","volume":"20","author":"Alon Noga","year":"2000","unstructured":"Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy (2000) Efficient testing of large graphs. Combinatorica 20(6): 451\u2013476","journal-title":"Combinatorica"},{"key":"92_CR3","doi-asserted-by":"crossref","unstructured":"Noga Alon, Eldar Fischer, Ilan Newman & Asaf Shapira (2006). A combinatorial characterization of the testable graph properties: it\u2019s all about regularity. In STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 251\u2013260.","DOI":"10.1145\/1132516.1132555"},{"key":"92_CR4","unstructured":"Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn & Dana Ron (2003). Testing low-degree polynomials over GF(2). In Random\u201903: Proceedings of 7th International Workshop on Randomization and Computation, 188\u2013199. URL citeseer.ist.psu.edu\/article\/alon03testing.htm ."},{"key":"92_CR5","doi-asserted-by":"crossref","unstructured":"Noga Alon, Michael Krivelevich, Ilan Newman & Mario Szegedy (2000b). Regular Languages are Testable with a Constant Number of Queries. SIAM Journal on Computing 30(6), 1842\u20131862.","DOI":"10.1137\/S0097539700366528"},{"issue":"3","key":"92_CR6","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/j.jcss.2004.04.008","volume":"69","author":"Alon Noga","year":"2004","unstructured":"Noga Alon, Asaf Shapira (2004) Testing subgraphs in directed graphs. Journal of Computer and System Sciences 9(3): 354\u2013382","journal-title":"Journal of Computer and System Sciences"},{"key":"92_CR7","doi-asserted-by":"crossref","unstructured":"Noga Alon & Asaf Shapira (2005a). A Characterization of the (natural) Graph Properties Testable with One-Sided Error. In FOCS\u201905: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 429\u2013438. IEEE Computer Society. ISBN 0-7695-2468-0.","DOI":"10.1109\/SFCS.2005.5"},{"key":"92_CR8","doi-asserted-by":"crossref","unstructured":"Noga Alon & Asaf Shapira (2005b). Every monotone graph property is testable. In STOC\u201905: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 128\u2013137. ACM. ISBN 1-58113-960-8.","DOI":"10.1145\/1060590.1060611"},{"key":"92_CR9","unstructured":"Tim Austin & Terence Tao (2008). On the testability and repair of hereditary hypergraph properties. http:\/\/arxiv.org\/abs\/0801.2179 ."},{"issue":"2","key":"92_CR10","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1109\/TPAMI.1987.4767904","volume":"9","author":"Bailey Thomas","year":"1987","unstructured":"Thomas Bailey, John Cowles (1987). A convex hull inclusion test. IEEE Transactions on Pattern Analysis and Machine Intelligence 9(2): 312\u2013316","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"92_CR11","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Prahladh Harsha & Sofya Raskhodnikova (2005). Some 3CNF Properties Are Hard to Test. SIAM Journal on Computing 35(1), 1\u201321. Early version in STOC\u201903.","DOI":"10.1137\/S0097539704445445"},{"key":"92_CR12","unstructured":"Arnab Bhattacharyya, Victor Chen, Madhu Sudan & Ning Xie (2009). Testing linear-invariant non-linear properties. In STACS\u201909: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 135\u2013146."},{"key":"92_CR13","doi-asserted-by":"crossref","unstructured":"Arnab Bhattacharyya & Ning Xie (2010). Lower bounds on testing triangle-freeness in Boolean functions. In SODA\u201910: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 87\u201398.","DOI":"10.1137\/1.9781611973075.9"},{"key":"92_CR14","doi-asserted-by":"crossref","unstructured":"Christian Borgs, Jennifer T. Chayes, L\u00e1szl\u00f3 Lov\u00e1sz, Vera T. S\u00f3s, Bal\u00e1zs Szegedy & Katalin Vesztergombi (2006). Graph limits and parameter testing. In STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 261\u2013270.","DOI":"10.1145\/1132516.1132556"},{"key":"92_CR15","unstructured":"Henri Cohen (2000). A Course in Computational Algebraic Number Theory. Springer."},{"key":"92_CR16","doi-asserted-by":"crossref","unstructured":"Henry Cohn, Robert Kleinbergy, Bal\u00e1zs Szegedy & Christopher Umans (2005). Group-theoretic algorithms for matrix multiplication. In FOCS\u201905: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 379\u2013388.","DOI":"10.1109\/SFCS.2005.39"},{"key":"92_CR17","doi-asserted-by":"crossref","unstructured":"Don Coppersmith & Shmuel Winograd (1990). Matrix Multiplication via Arithmetic Progressions. Journal of Symbolic Computation 9, 251\u2013280. Earlier version in STOC\u201987.","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"92_CR18","doi-asserted-by":"crossref","unstructured":"Eric Domenjoud (1991). Solving Systems of Linear Diophantine Equations: an Algebraic Approach. In In Proc. 16th Mathematical Foundations of Computer Science, Warsaw, LNCS 520, 141\u2013150. Springer-Verlag.","DOI":"10.1007\/3-540-54345-7_57"},{"issue":"1","key":"92_CR19","doi-asserted-by":"crossref","first-page":"561","DOI":"10.4007\/annals.2011.174.1.17","volume":"174","author":"Fox Jacob","year":"2011","unstructured":"Jacob Fox (2011) A new proof of the graph removal lemma. Annals of Mathematics 174(1): 561\u2013579","journal-title":"Annals of Mathematics"},{"key":"92_CR20","unstructured":"Hu Fu & Robert Kleinberg (2013). Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. http:\/\/arxiv.org\/abs\/1308.1643 ."},{"key":"92_CR21","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property testing and its connection to learning and approximation. Journal of the ACM 45(4), 653\u2013750. ISSN 0004-5411.","DOI":"10.1145\/285055.285060"},{"issue":"1","key":"92_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/rsa.10078","volume":"23","author":"Goldreich Oded","year":"2003","unstructured":"Oded Goldreich, Luca Trevisan (2003) Three theorems regarding testing graph properties. Random Structures and Algorithms 23(1): 23\u201357","journal-title":"Random Structures and Algorithms"},{"key":"92_CR23","doi-asserted-by":"crossref","unstructured":"Ben Green (2005). A Szemer\u00e9di-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal. 15(2), 340\u2013376. ISSN 1016-443X.","DOI":"10.1007\/s00039-005-0509-8"},{"key":"92_CR24","volume-title":"Convex and Discrete Geometry","author":"Gruber Peter","year":"2007","unstructured":"Peter Gruber (2007) Convex and Discrete Geometry. Springer, New York"},{"key":"92_CR25","unstructured":"Pooya Hatami, Sushant Sachdeva & Madhur Tulsiani (2013). An Arithmetic Analogue of Fox\u2019s Triangle Removal Argument. http:\/\/arxiv.org\/abs\/1304.4921 ."},{"key":"92_CR26","unstructured":"Ishay Haviv & Ning Xie (2013). Sunflowers and Testing Triangle-Freeness of Functions. Manuscript."},{"key":"92_CR27","doi-asserted-by":"crossref","unstructured":"Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra & David Zuckerman (2004). Testing low-degree polynomials over prime fields. In FOCS\u201904: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 423\u2013432.","DOI":"10.1109\/FOCS.2004.64"},{"key":"92_CR28","unstructured":"Tali Kaufman & Dana Ron (2004). Testing polynomials over general fields. In FOCS\u201904: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 413\u2013422."},{"key":"92_CR29","doi-asserted-by":"crossref","unstructured":"Tali Kaufman & Madhu Sudan (2008). Algebraic Property Testing: The Role of Invariance. In STOC\u201908: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 403\u2013412.","DOI":"10.1145\/1374376.1374434"},{"issue":"4","key":"92_CR30","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.jcta.2008.12.003","volume":"116","author":"Kr\u00e1l\u2019 Daniel","year":"2009","unstructured":"Daniel Kr\u00e1l\u2019, Oriol Serra, Llu\u00eds Vena (2009). A combinatorial proof of the Removal Lemma for Groups. Journal of Combinatorial Theory 116(4): 971\u2013978","journal-title":"Journal of Combinatorial Theory"},{"key":"92_CR31","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s11856-011-0080-y","volume":"187","author":"Kr\u00e1l\u2019 Daniel","year":"2012","unstructured":"Daniel Kr\u00e1l\u2019, Oriol Serra, Llu\u00eds Vena (2012). A Removal Lemma for Systems of Linear Equations over Finite Fields. Israel Journal of Mathematics 187, 193\u2013207","journal-title":"Israel Journal of Mathematics"},{"key":"92_CR32","unstructured":"Florence J. MacWilliams & Neil J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland."},{"key":"92_CR33","doi-asserted-by":"crossref","unstructured":"Michal Parnas, Dana Ron & Alex Samorodnitsky (2003). Testing Basic Boolean Formulae. SIAM Journal on Discrete Mathematics 16(1), 20\u201346. ISSN 0895-4801.","DOI":"10.1137\/S0895480101407444"},{"key":"92_CR34","doi-asserted-by":"crossref","unstructured":"Vojt\u011bch R\u00f6dl & Mathias Schacht (2009). Generalizations of the Removal Lemma. Combinatorica 29(4), 467\u2013501. Earlier version in STOC\u201907.","DOI":"10.1007\/s00493-009-2320-x"},{"key":"92_CR35","doi-asserted-by":"crossref","unstructured":"Ronitt Rubinfeld & Madhu Sudan (1996). Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2), 252\u2013271. citeseer.ist.psu.edu\/rubinfeld96robust.htm .","DOI":"10.1137\/S0097539793255151"},{"key":"92_CR36","doi-asserted-by":"crossref","unstructured":"Asaf Shapira (2009). Green\u2019s conjecture and testing linear-invariant properties. In STOC\u201909: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 159\u2013166.","DOI":"10.1145\/1536414.1536438"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0092-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-014-0092-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0092-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T14:39:24Z","timestamp":1747147164000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-014-0092-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,6]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["92"],"URL":"https:\/\/doi.org\/10.1007\/s00037-014-0092-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2014,11,6]]}}}