{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T08:34:25Z","timestamp":1790843665117,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132555","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T12:53:01Z","timestamp":1153745581000},"page":"251-260","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["A combinatorial characterization of the testable graph properties"],"prefix":"10.1145","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel-Aviv University and IAS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eldar","family":"Fischer","sequence":"additional","affiliation":[{"name":"Israel Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[{"name":"Haifa University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[{"name":"Tel-Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796550"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796495"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366528"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199358655"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060611"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_25"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780594"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132556"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647910.740467"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444199X"},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. of the 12th SODA","author":"Fischer E.","year":"2001","unstructured":"E. Fischer , Testing graphs for colorability properties , Proc. of the 12th SODA ( 2001 ), 873--882.]] E. Fischer, Testing graphs for colorability properties, Proc. of the 12th SODA (2001), 873--882.]]"},{"key":"e_1_3_2_1_15_1","first-page":"97","article-title":"The art of uninformed decisions: A primer to property testing","volume":"75","author":"Fischer E.","year":"2001","unstructured":"E. Fischer , The art of uninformed decisions: A primer to property testing , The Computational Complexity Column of The Bulletin of the EATCS 75 ( 2001 ), 97 -- 126 .]] E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the EATCS 75 (2001), 97--126.]]","journal-title":"The Computational Complexity Column of The Bulletin of the EATCS"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970445603"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.757577"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060612"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10110"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060614"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_3_2_1_23_1","volume-title":"Combinatorial property testing - a survey","author":"Goldreich O.","year":"1998","unstructured":"O. Goldreich , Combinatorial property testing - a survey , In : Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMS-DIMACS ( 1998 ), 45--60.]] O. Goldreich, Combinatorial property testing - a survey, In: Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMS-DIMACS (1998), 45--60.]]"},{"key":"e_1_3_2_1_24_1","volume-title":"Contemplations on testing graph properties, manuscript","author":"Goldreich O.","year":"2005","unstructured":"O. Goldreich , Contemplations on testing graph properties, manuscript , 2005 .]] O. Goldreich, Contemplations on testing graph properties, manuscript, 2005.]]"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258627"},{"key":"e_1_3_2_1_28_1","volume-title":"Combinatorics, Paul Erd\u00f6s is Eighty, Vol II","author":"Koml\u00f3s J.","year":"1996","unstructured":"J. Koml\u00f3s and M. Simonovits , Szemer\u00e9di's Regularity Lemma and its applications in graph theory . In: Combinatorics, Paul Erd\u00f6s is Eighty, Vol II (D. Mikl\u00f3s, V. T. S\u00f3s, T. Sz\u00f6nyi eds.), J\u00e1nos Bolyai Math. Soc., Budapest ( 1996 ), 295--352.]] J. Koml\u00f3s and M. Simonovits, Szemer\u00e9di's Regularity Lemma and its applications in graph theory. In: Combinatorics, Paul Erd\u00f6s is Eighty, Vol II (D. Mikl\u00f3s, V. T. S\u00f3s, T. Sz\u00f6nyi eds.), J\u00e1nos Bolyai Math. Soc., Budapest (1996), 295--352.]]"},{"key":"e_1_3_2_1_29_1","volume-title":"Graph limits and testing hereditary graph properties, manuscript","author":"Lov\u00e1sz L.","year":"2005","unstructured":"L. Lov\u00e1sz and B. Szegedy , Graph limits and testing hereditary graph properties, manuscript , 2005 .]] L. Lov\u00e1sz and B. Szegedy, Graph limits and testing hereditary graph properties, manuscript, 2005.]]"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796549"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10067"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582932"},{"key":"e_1_3_2_1_34_1","volume-title":"Handbook of Randomized Computing","year":"2001","unstructured":"Property testing , in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing , Vol. II , Kluwer Academic Publishers , 2001 , 597--649.]] Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, 2001, 597--649.]]"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_36_1","volume-title":"Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.)","author":"Szemer\u00e9di E.","year":"1978","unstructured":"E. Szemer\u00e9di , Regular partitions of graphs , In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.) , 1978 , 399--401.]] E. Szemer\u00e9di, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.), 1978, 399--401.]]"}],"event":{"name":"STOC06: Symposium on Theory of Computing","location":"Seattle WA USA","acronym":"STOC06","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132555","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132555","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:50Z","timestamp":1750249130000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132555"}},"subtitle":["it's all about regularity"],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":36,"alternative-id":["10.1145\/1132516.1132555","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132555","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}