{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,18]],"date-time":"2026-10-18T05:31:09Z","timestamp":1792301469346,"version":"4.4.0"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemer\u00e9di's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemer\u00e9di-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property ${\\cal P}$ can be tested with a constant number of queries if and only if testing ${\\cal P}$ can be reduced to testing the property of satisfying one of finitely many Szemer\u00e9di-partitions. This means that in some sense, testing for Szemer\u00e9di-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653\u2013750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.<\/jats:p>","DOI":"10.1137\/060667177","type":"journal-article","created":{"date-parts":[[2009,5,29]],"date-time":"2009-05-29T12:34:17Z","timestamp":1243600457000},"page":"143-167","source":"Crossref","is-referenced-by-count":80,"title":["A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity"],"prefix":"10.1137","volume":"39","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eldar","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,5,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102410973"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366528"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199358655"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"R8","unstructured":"N. Alon and A. Shapira,\n                      A separation theorem in property testing\n                      , Combinatorica, to appear."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd edition, John Wiley & Sons, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20182"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"C. Borgs, J. Chayes, L. Lov\u00e1sz, V. T. S\u00f3s, B. Szegedy, and K. Vesztergombi,\n                      Graph limits and parameter testing\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, 2006, ACM, New York, 2006, pp. 261\u2013270.","DOI":"10.1145\/1132516.1132556"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. Czumaj, C. Sohler, and M. Ziegler,\n                      Property testing in computational geometry\n                      , in Proceedings of the Eighth Annual European Symposium, Saarbrucken, Germany, 2000, Lecture Notes in Comput. Sci. 1879, Springer, Berlin, 2000, pp. 155\u2013166.","DOI":"10.1007\/3-540-45253-2_15"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444199X"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20037"},{"key":"R17","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci. EATCS"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970445603"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/060652324"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10110"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky,\n                      Monotonicity testing over general poset domains\n                      , Proc. of STOC (2002), pp. 474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"K. Friedl, G. Ivanyos, and M. Santha,\n                      Efficient testing of groups\n                      , in Proceedings of the 37th Annual STOC, Baltimore, MD, 2005, pp. 157\u2013166.","DOI":"10.1145\/1060590.1060614"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Combinatorial property testing (a survey)\n                      , in Randomization Methods in Algorithm Design, P. Pardalos, S. Rajasekaran, and J. Rolim, eds., DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 43, AMS, Providence, RI, 1999, pp. 45\u201359.","DOI":"10.1090\/dimacs\/043\/04"},{"key":"R26","unstructured":"O. Goldreich,\n                      Contemplations on testing graph properties\n                      , manuscript, 2005; available online at http:\/\/www.wisdom.weizmann.ac.il\/~oded."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"R31","unstructured":"J. Koml\u00f3s and M. Simonovits,\n                      Szemer\u00e9di's regularity lemma and its applications in graph theory\n                      , in Combinatorics, Paul Erd\u0151s is Eighty, Vol II, D. Mikl\u00f3s, V. T. S\u00f3s, and T. Sz\u00f6nyi, eds., J\u00e1nos Bolyai Math. Soc., Budapest, 1996, pp. 295\u2013352."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"I. Newman,\n                      Testing of functions that have small width branching programs\n                      , in Proceedings of the 41st Annual Symposium on FOCS, Redondo Beach, CA, 2000, pp. 251\u2013258.","DOI":"10.1109\/SFCS.2000.892112"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10067"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582932"},{"key":"R36","unstructured":"D. Ron,\n                      Property testing\n                      , in Handbook of Randomized Computing, P. M. Pardalos, S. Rajasekaran, J. Reif, and J. D. P. Rolim, eds., Vol. II, Kluwer Academic Publishers, Dordrecht, 2001, pp. 597\u2013649."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R38","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Colloq. Internat. CNRS, J. C. Bermond, J. C. Fournier, M. Las Vergnas, and D. Sotteau, eds., CNRS, Paris, 1978, pp. 399\u2013401."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060667177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:45Z","timestamp":1787336385000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060667177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060667177"],"URL":"https:\/\/doi.org\/10.1137\/060667177","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}