{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T10:43:34Z","timestamp":1762253014682,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s11083-019-09494-3","type":"journal-article","created":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T08:03:41Z","timestamp":1558598621000},"page":"83-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Removal Lemmas for Matrices"],"prefix":"10.1007","volume":"37","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6366-5964","authenticated-orcid":false,"given":"Omri","family":"Ben-Eliezer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,23]]},"reference":[{"key":"9494_CR1","first-page":"359","volume":"21","author":"N Alon","year":"2002","unstructured":"Alon, N.: Testing subgraphs in large graphs. Proc. 42th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 2001, 434\u2013441; also Random Structures & Algorithms 21, 359\u2013370 (2002)","journal-title":"Proc. 42th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 2001, 434\u2013441; also Random Structures & Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Ben-Eliezer, O., Fischer, E.: Testing hereditary properties of ordered graphs and matrices. In: Proc. 58th Annu. Symp. Foundations of Computer Science (FOCS), pp 848\u2013858. IEEE (2017)","key":"9494_CR2","DOI":"10.1109\/FOCS.2017.83"},{"key":"9494_CR3","first-page":"80","volume":"16","author":"N Alon","year":"1994","unstructured":"Alon, N., Duke, R.A., Lefmann, H., R\u00f6dl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. Proc. 33th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1992, 473\u2013481; also Journal of Algorithms 16, 80\u2013109 (1994)","journal-title":"Proc. 33th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1992, 473\u2013481; also Journal of Algorithms"},{"key":"9494_CR4","first-page":"451","volume":"20","author":"N Alon","year":"2000","unstructured":"Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs. Proc. 40th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1999, 656\u2013666; also Combinatorica 20, 451\u2013476 (2000)","journal-title":"Proc. 40th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1999, 656\u2013666; also Combinatorica"},{"key":"9494_CR5","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1137\/050627915","volume":"37","author":"N Alon","year":"2007","unstructured":"Alon, N., Fischer, E., Newman, I.: Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM J. Comput 37, 959\u2013976 (2007)","journal-title":"SIAM J. Comput"},{"key":"9494_CR6","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1017\/S0963548314000765","volume":"24","author":"N Alon","year":"2015","unstructured":"Alon, N., Fox, J.: Easily testable graph properties. Combin. Probab. Comput. 24, 646\u2013657 (2015)","journal-title":"Combin. Probab. Comput."},{"key":"9494_CR7","first-page":"1842","volume":"30","author":"N Alon","year":"2001","unstructured":"Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. Proc. 40th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1999, 645\u2013655; also SIAM J. Comput. 30, 1842\u20131862 (2001)","journal-title":"Proc. 40th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1999, 645\u2013655; also SIAM J. Comput."},{"key":"9494_CR8","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1017\/S0963548306007759","volume":"15","author":"N Alon","year":"2006","unstructured":"Alon, N., Shapira, A.: A characterization of easily testable induced subgraphs. Combin. Probab. Comput. 15, 791\u2013805 (2006)","journal-title":"Combin. Probab. Comput."},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error, SIAM J. Comput. 37 (2008), 1703-1727","key":"#cr-split#-9494_CR9.1","DOI":"10.1137\/06064888X"},{"unstructured":"also Proc. 46th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 429-438 (2005)","key":"#cr-split#-9494_CR9.2"},{"key":"9494_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"32","author":"F Behrend","year":"1946","unstructured":"Behrend, F.: On sets of integers which contain no three terms in arithmetic progression. Proc. Nat. Acad. Sci. 32, 331\u2013332 (1946)","journal-title":"Proc. Nat. Acad. Sci."},{"unstructured":"Ben-Eliezer, O., Fischer, E.: Earthmover resilience and testing in ordered structures. In: Proc. IEEE 33rd Computational Complexity Conference (CCC), pp 18:1\u201318:35 (2018)","key":"9494_CR11"},{"unstructured":"Ben-Eliezer, O., Fischer, E., Levi, A., Yoshida, Y.: Limits of ordered graphs and images. arXiv:\n1811.02023","key":"9494_CR12"},{"unstructured":"Ben-Eliezer, O., Korman, S., Reichman, D.: Deleting and testing forbidden patterns in multi-dimensional arrays. In: Proc. 44th Int. Colloq. Automata Languages Programming (ICALP), pp 9:1\u20139:14 (2017)","key":"9494_CR13"},{"key":"9494_CR14","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1007\/s00039-012-0171-x","volume":"22","author":"D Conlon","year":"2012","unstructured":"Conlon, D., Fox, J.: Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22, 1191\u20131256 (2012)","journal-title":"Geom. Funct. Anal."},{"key":"9494_CR15","volume-title":"Graph Removal Lemmas, Surveys in Combinatorics 2013, 1\u201349, London Math. Soc Lecture Note Ser, vol. 409","author":"D Conlon","year":"2013","unstructured":"Conlon, D., Fox, J.: Graph Removal Lemmas, Surveys in Combinatorics 2013, 1\u201349, London Math. Soc Lecture Note Ser, vol. 409. Cambridge University Press, Cambridge (2013)"},{"key":"9494_CR16","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00493-007-2154-3","volume":"27","author":"E Fischer","year":"2007","unstructured":"Fischer, E., Newman, I.: Testing of matrix-poset properties. Combinatorica 27, 293\u2013327 (2007)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Fischer, E., Rozenberg, E.: Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects. Proc. RANDOM, 464\u2013478 (2007)","key":"9494_CR17","DOI":"10.1007\/978-3-540-74208-1_34"},{"key":"9494_CR18","doi-asserted-by":"publisher","first-page":"561","DOI":"10.4007\/annals.2011.174.1.17","volume":"174","author":"J Fox","year":"2011","unstructured":"Fox, J.: A new proof of the graph removal lemma. Ann. of Math. 174, 561\u2013579 (2011)","journal-title":"Ann. of Math."},{"doi-asserted-by":"crossref","unstructured":"Gishboliner, L., Shapira, A.: Removal lemmas with polynomial bounds. In: Proc. 49th ACM SIGACT Symp Theory of Computing (STOC), pp 510\u2013522 (2017)","key":"9494_CR19","DOI":"10.1145\/3055399.3055404"},{"key":"9494_CR20","first-page":"653","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Proc. 37th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1996, 339\u2013348; also J. ACM 45, 653\u2013750 (1998)","journal-title":"Proc. 37th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1996, 339\u2013348; also J. ACM"},{"key":"9494_CR21","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","volume":"11","author":"T Gowers","year":"2001","unstructured":"Gowers, T.: A new proof of Szemer\u00e9di\u2019s theorem. Geom. Funct. Anal. 11, 465\u2013588 (2001)","journal-title":"Geom. Funct. Anal."},{"doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Szegedy, B.: Regularity partitions and the topology of graphons, in An irregular mind, 415\u2013445, Bolyai Soc. Math. Stud. 21, J\u00e1nos Bolyai Math. Soc., Budapest (2010)","key":"9494_CR22","DOI":"10.1007\/978-3-642-14444-8_12"},{"key":"9494_CR23","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1002\/rsa.20117","volume":"28","author":"B Nagle","year":"2006","unstructured":"Nagle, B., Ro\u030bdl, V., Schacht, M.: The counting lemma for regular k-uniform hypergraphs. Random Struct. Algoritm. 28, 113\u2013179 (2006)","journal-title":"Random Struct. Algoritm."},{"key":"9494_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20017","volume":"25","author":"V R\u00f6dl","year":"2004","unstructured":"R\u00f6dl, V., Skokan, J.: Regularity lemma for uniform hypergraphs. Random Struct. Algoritm. 25, 1\u201342 (2004)","journal-title":"Random Struct. Algoritm."},{"key":"9494_CR25","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. Siam. J. Comput. 25, 252\u2013271 (1996)","journal-title":"Siam. J. Comput."},{"unstructured":"Ruzsa, I.Z., Szemer\u00e9di, E.: Triple Systems with No Six Points Carrying Three Triangles, Combinatorics, Vol. II, 939\u2013945, Coll. Math. Soc. J. Bolyai 18, North-Holland, Amsterdam-New York (1978)","key":"9494_CR26"},{"doi-asserted-by":"crossref","unstructured":"Sudan, M.: Invariance in property testing. In: Goldreich, O. (ed.) Property Testing: Current Research and Surveys. Vol. 6390 of Lecture Notes in Computer Science, pp 211\u2013227. Springer (2010)","key":"9494_CR27","DOI":"10.1007\/978-3-642-16367-8_12"},{"unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs, in probl\u00e8mes Combinatoires et th\u00e9orie des Graphes, Colloq. Internat. CNRS 260, Orsay, 399\u2013401 (1976)","key":"9494_CR28"},{"key":"9494_CR29","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1016\/j.jcta.2005.11.006","volume":"113","author":"T Tao","year":"2006","unstructured":"Tao, T.: A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113, 1257\u20131280 (2006)","journal-title":"J. Combin. Theory Ser. A"}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-019-09494-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11083-019-09494-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-019-09494-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,24]],"date-time":"2020-05-24T16:03:16Z","timestamp":1590336196000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11083-019-09494-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,23]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9494"],"URL":"https:\/\/doi.org\/10.1007\/s11083-019-09494-3","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"type":"print","value":"0167-8094"},{"type":"electronic","value":"1572-9273"}],"subject":[],"published":{"date-parts":[[2019,5,23]]},"assertion":[{"value":"27 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}