{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T14:23:19Z","timestamp":1776694999056,"version":"3.51.2"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T00:00:00Z","timestamp":1464566400000},"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":[[2017,6]]},"DOI":"10.1007\/s00037-016-0138-7","type":"journal-article","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T09:22:32Z","timestamp":1464600152000},"page":"497-530","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Sunflowers and Testing Triangle-Freeness of Functions"],"prefix":"10.1007","volume":"26","author":[{"given":"Ishay","family":"Haviv","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,30]]},"reference":[{"issue":"3-4","key":"138_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.10056","volume":"21","author":"Noga Alon","year":"2002","unstructured":"Alon Noga (2002) Testing subgraphs in large graphs. Random Struct. Algorithms 21(3-4): 359\u2013370 Preliminary version in Foundations of\nComputer Science\u201901","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"138_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"Noga Alon","year":"1987","unstructured":"Alon Noga, Boppana Ravi B. (1987) The monotone circuit com plexity of Boolean functions. Combinatorica 7(1): 1\u201322","journal-title":"Combinatorica"},{"key":"138_CR3","doi-asserted-by":"publisher","unstructured":"Noga Alon, Eldar Fischer, Ilan Newman & Asaf Shapira (2009). A Combinatorial Characterization of the Testable Graph Properties: It\u2019s All About Regularity. SIAM J. Comput. 39(1), 143\u2013167. Preliminary version in Symposium on Theory of Computing\u201906.","DOI":"10.1137\/060667177"},{"issue":"1","key":"138_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548315000292","volume":"25","author":"Noga Alon","year":"2016","unstructured":"Alon Noga, Hod Rani, Weinstein Amit (2016) On Active and Passive Testing. Combinatorics, Probability & Computing 25(1): 1\u201320","journal-title":"Combinatorics, Probability & Computing"},{"issue":"2","key":"138_CR5","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00037-013-0060-1","volume":"22","author":"Noga Alon","year":"2013","unstructured":"Alon Noga, Shpilka Amir, Umans Christopher (2013) On sunflowers and matrix multiplication. Computational Complexity 22(2): 219\u2013243 Preliminary version in CCC\u201912","journal-title":"Computational Complexity"},{"issue":"2","key":"138_CR6","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1090\/S0894-0347-2011-00725-X","volume":"25","author":"Michael Bateman","year":"2012","unstructured":"Bateman Michael, Katz Nets Hawk (2012) New bounds on cap sets. J. Amer. Math. Soc. 25(2): 585\u2013613","journal-title":"J. Amer. Math. Soc."},{"issue":"12","key":"138_CR7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"32","author":"F. A. Behrend","year":"1946","unstructured":"Behrend F. A. (1946) On Sets of Integers Which Contain No Three Terms in Arithmetical Progression. Proc. National Academy of Sciences USA 32(12): 331\u2013332","journal-title":"Proc. National Academy of Sciences USA"},{"issue":"4","key":"138_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/2556663.2556678","volume":"44","author":"Arnab Bhattacharyya","year":"2013","unstructured":"Bhattacharyya Arnab (2013) Guest column: On testing affine invariant properties over finite fields. SIGACT News 44(4): 53\u201372","journal-title":"SIGACT News"},{"key":"138_CR9","doi-asserted-by":"publisher","unstructured":"Arnab Bhattacharyya, Elena Grigorescu & Asaf Shapira (2015). A unified framework for testing linear-invariant properties. Random Struct. Algorithms 46(2), 232\u2013260. Preliminary version in Foundations of Computer Science\u201910.","DOI":"10.1002\/rsa.20507"},{"key":"138_CR10","doi-asserted-by":"publisher","unstructured":"Arnab Bhattacharyya & Ning Xie (2015). Lower bounds for testing triangle-freeness in Boolean functions. Computational Complexity 24(1), 65\u2013101. Preliminary version in SODA\u201910.","DOI":"10.1007\/s00037-014-0092-1"},{"key":"138_CR11","doi-asserted-by":"publisher","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 Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, 261\u2013270.","DOI":"10.1145\/1132516.1132556"},{"key":"138_CR12","doi-asserted-by":"publisher","unstructured":"Henry Cohn, Robert D. Kleinberg, Bal\u00e1zs Szegedy & Christopher Umans (2005). Group-theoretic Algorithms for Matrix Multiplication. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 379\u2013388.","DOI":"10.1109\/SFCS.2005.39"},{"issue":"3","key":"138_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"Don Coppersmith","year":"1990","unstructured":"Coppersmith Don, Winograd Shmuel (1990) Matrix Multipli cation via Arithmetic Progressions. J. Symb. Comput. 9(3): 251\u2013280 Preliminary version in Symposium on Theory of Computing\u201987","journal-title":"J. Symb. Comput."},{"issue":"1","key":"138_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"Irit Dinur","year":"2005","unstructured":"Dinur Irit, Safra Shmuel (2005) On the hardness of approximating minimum vertex cover. Annals of Mathematics 162(1): 439\u2013485 Preliminary version in Symposium on Theory of Computing\u201902","journal-title":"Annals of Mathematics"},{"issue":"1","key":"138_CR15","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1027365901231","volume":"31","author":"Yves Edel","year":"2004","unstructured":"Edel Yves (2004) Extensions of Generalized Product Caps. Des. Codes Cryptography 31(1): 5\u201314","journal-title":"Des. Codes Cryptography"},{"issue":"1","key":"138_CR16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s11856-011-0061-1","volume":"184","author":"Michael Elkin","year":"2011","unstructured":"Elkin Michael (2011) An improved construction of progression-free sets. Israel J. of Math. 184(1): 93\u2013128 Preliminary version in SODA\u201910","journal-title":"Israel J. of Math."},{"key":"138_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s P., Rado R. (1960) Intersection sets. J. London Math. Soc. 35: 85\u201390","journal-title":"J. London Math. Soc."},{"issue":"3","key":"138_CR18","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0097-3165(78)90060-2","volume":"24","author":"Paul Erd\u00f6s","year":"1978","unstructured":"Erd\u00f6s Paul, Szemer\u00e9di Endre (1978) Combinatorial Properties of Systems of Sets. J. Comb. Theory, Ser. A 24(3): 308\u2013313","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"1","key":"138_CR19","doi-asserted-by":"publisher","first-page":"561","DOI":"10.4007\/annals.2011.174.1.17","volume":"174","author":"Jacob Fox","year":"2011","unstructured":"Fox Jacob (2011) A new proof of the graph removal lemma. Annals of Mathematics 174(1): 561\u2013579","journal-title":"Annals of Mathematics"},{"key":"138_CR20","unstructured":"Hu Fu & Robert Kleinberg (2014). Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. In RANDOM, 669\u2013676."},{"key":"138_CR21","doi-asserted-by":"publisher","unstructured":"Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property Testing and its Connection to Learning and Approximation. J. ACM 45(4), 653\u2013750. Preliminary version in Foundations of Computer Science\u201996.","DOI":"10.1145\/285055.285060"},{"issue":"2","key":"138_CR22","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/s00039-005-0509-8","volume":"15","author":"Ben Green","year":"2005","unstructured":"Green Ben (2005) A Szemer\u00e9di-type regularity lemma in Abelian groups. Geom. and Funct. Anal. 15(2): 340\u2013376","journal-title":"Geom. and Funct. Anal."},{"key":"138_CR23","unstructured":"Pooya Hatami, Sushant Sachdeva & Madhur Tulsiani (2013). An Arithmetic Analogue of Fox\u2019s Triangle Removal Argument. CoRR \n                        arXiv:1304.4921\n                        \n                    ."},{"key":"138_CR24","doi-asserted-by":"publisher","unstructured":"Tali Kaufman & Madhu Sudan (2008). Algebraic property testing: the role of invariance. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 403\u2013412.","DOI":"10.1145\/1374376.1374434"},{"key":"138_CR25","unstructured":"A. V. Kostochka (1997). A Bound of the Cardinality of Families not Containing \n\n$${\\Delta}$$\n                        \n                            \n                                            \n                                \u0394\n                            \n                        \n                    -Systems. In The Mathematics of Paul Erd\u00f6s II, Algorithms and Combinatorics, volume 14, 229\u2013235. Springer, Berlin."},{"issue":"4","key":"138_CR26","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/j.jcta.2008.12.003","volume":"116","author":"Daniel Kr\u00e1l\u2019","year":"2009","unstructured":"Kr\u00e1l\u2019 Daniel, Serra Oriol, Vena Llu\u00eds (2009) A combinatorial proof of the Removal Lemma for Groups. J. Comb. Theory, Ser. A 116(4): 971\u2013978","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"1","key":"138_CR27","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s11856-011-0080-y","volume":"187","author":"Daniel Kr\u00e1l\u2019","year":"2012","unstructured":"Kr\u00e1l\u2019 Daniel, Serra Oriol, Vena Llu\u00eds (2012) A removal lemma for systems of linear equations over finite fields. Israel J. of Math. 187(1): 193\u2013207","journal-title":"Israel J. of Math."},{"key":"138_CR28","doi-asserted-by":"publisher","unstructured":"Jacobus H. van Lint & Richard M. Wilson (2001). A course in combinatorics. Cambridge University Press, 2nd edition.","DOI":"10.1017\/CBO9780511987045"},{"key":"138_CR29","doi-asserted-by":"publisher","unstructured":"Yu-Ru Liu & Craig V. Spencer (2009). A generalization of Meshulam\u2019s theorem on subsets of finite Abelian groups with no 3-term arithmetic progression. Des. Codes Cryptography 52(1): 83\u201391","DOI":"10.1007\/s10623-009-9268-0"},{"issue":"1","key":"138_CR30","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0097-3165(95)90024-1","volume":"71","author":"Roy Meshulam","year":"1995","unstructured":"Meshulam Roy (1995) On Subsets of Finite Abelian Groups with No 3-Term Arithmetic Progressions. J. Comb. Theory, Ser. A 71(1): 168\u2013172","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"2","key":"138_CR31","first-page":"354","volume":"31","author":"Alexander A. Razborov","year":"1985","unstructured":"Razborov Alexander A. (1985) Lower bounds for the monotone complexity of some Boolean functions. Soviet Mathematics Doklady 31(2): 354\u2013357","journal-title":"Soviet Mathematics Doklady"},{"key":"138_CR32","doi-asserted-by":"publisher","unstructured":"Ronitt Rubinfeld & Madhu Sudan (1996). Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2), 252\u2013271. Preliminary version in SODA\u201992.","DOI":"10.1137\/S0097539793255151"},{"issue":"12","key":"138_CR33","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1073\/pnas.28.12.561","volume":"28","author":"R. Salem","year":"1942","unstructured":"Salem R., Spencer D. C. (1942) On Sets of IntegersWhich Contain No Three Terms in Arithmetical Progression. Proc. National Academy of Sciences USA 28(12): 561\u2013563","journal-title":"Proc. National Academy of Sciences USA"},{"key":"138_CR34","doi-asserted-by":"publisher","unstructured":"Asaf Shapira (2010). A proof of Green\u2019s conjecture regarding the removal properties of sets of linear equations. J. London Math. Soc. 81(2), 355\u2013373. Preliminary version in Symposium on Theory of Computing\u201909.","DOI":"10.1112\/jlms\/jdp076"},{"key":"138_CR35","unstructured":"Andrew James Stothers (2010). On the complexity of matrix multiplication. Ph.D. thesis, The University of Edinburgh."},{"issue":"1","key":"138_CR36","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/1959045.1959062","volume":"42","author":"Madhu Sudan","year":"2011","unstructured":"Sudan Madhu (2011) Guest column: Testing linear properties: some general theme. SIGACT News 42(1): 59\u201380","journal-title":"SIGACT News"},{"key":"138_CR37","doi-asserted-by":"publisher","unstructured":"Virginia Vassilevska Williams (2012). Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, 887\u2013898.","DOI":"10.1145\/2213977.2214056"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0138-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0138-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0138-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0138-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0138-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,30]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["138"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0138-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,30]]}}}