{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:03Z","timestamp":1750307823939,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"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":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374433","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"393-402","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Every minor-closed property of sparse graphs is testable"],"prefix":"10.1145","author":[{"given":"Itai","family":"Benjamini","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"given":"Oded","family":"Schramm","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132555"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.5"},{"key":"e_1_3_2_1_4_1","volume-title":"Homomorphisms in graph property testing,in Topics in discrete mathematics, 281--313","author":"Alon N.","year":"2006","unstructured":"N. Alon and A. Shapira , Homomorphisms in graph property testing,in Topics in discrete mathematics, 281--313 , Springer , Berlin , 2006 . N. Alon and A. Shapira, Homomorphisms in graph property testing,in Topics in discrete mathematics, 281--313, Springer, Berlin,2006."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2321-1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652193"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132556"},{"key":"e_1_3_2_1_10_1","unstructured":"A. Czumaj A. Shapira and C. Sohler Testing hereditary propertiesof non-expanding bounded-degree graphs submitted (full version of CS1).  A. Czumaj A. Shapira and C. Sohler Testing hereditary propertiesof non-expanding bounded-degree graphs submitted (full version of CS1)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.69"},{"key":"e_1_3_2_1_12_1","first-page":"23","article-title":"Sublinear-time algorithms","volume":"89","author":"Czumaj A.","year":"2006","unstructured":"A. Czumaj and C. Sohler , Sublinear-time algorithms , Bulletin of theEATCS , 89 ( 2006 ) 23 -- 47 . A. Czumaj and C. Sohler, Sublinear-time algorithms, Bulletin of theEATCS, 89 (2006) 23--47.","journal-title":"Bulletin of theEATCS"},{"key":"e_1_3_2_1_13_1","volume-title":"Proc. of SODA","author":"Czumaj A.","year":"2007","unstructured":"A. Czumaj and C. Sohler , On testable properties in bounded degreegraphs , Proc. of SODA 2007 , 494--501. A. Czumaj and C. Sohler, On testable properties in bounded degreegraphs, Proc. of SODA 2007, 494--501."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_2_1_15_1","volume-title":"Graph Theory","author":"Diestel R.","year":"2005","unstructured":"R. Diestel , Graph Theory ( Third Edition), Springer , Heidenberg , 2005 . R. Diestel, Graph Theory (Third Edition), Springer, Heidenberg, 2005."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/3-540-60454-5_43","article-title":"The Complexity of LearningMinor-Closed Graph Classes","author":"Domingo C.","year":"1995","unstructured":"C. Domingo and J. Shawe-Taylor , The Complexity of LearningMinor-Closed Graph Classes , Proc. of Algorithmic Learning Theory 1995 , 249 -- 260 . C. Domingo and J. Shawe-Taylor, The Complexity of LearningMinor-Closed Graph Classes, Proc. of Algorithmic Learning Theory1995, 249--260.","journal-title":"Proc. of Algorithmic Learning Theory"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_1_18_1","unstructured":"G. Elek The combinatorial cost to appear in L'Enseignement Math\u00e9matique  G. Elek The combinatorial cost to appear in L'Enseignement Math\u00e9matique"},{"key":"e_1_3_2_1_19_1","volume-title":"A Regularity lemma for bounded degree graphs and itsapplications: parameter testing and infinite","author":"Elek G.","year":"2007","unstructured":"G. Elek , A Regularity lemma for bounded degree graphs and itsapplications: parameter testing and infinite volume limits,arXiv: 07112800 , 2007 . G. Elek, A Regularity lemma for bounded degree graphs and itsapplications: parameter testing and infinite volume limits,arXiv:07112800, 2007."},{"key":"e_1_3_2_1_20_1","first-page":"97","article-title":"The art of uninformed decisions: A primer to propertytesting","volume":"75","author":"Fischer E.","year":"2001","unstructured":"E. Fischer , The art of uninformed decisions: A primer to propertytesting , The Computational Complexity Column of The Bulletin ofthe European Association for Theoretical Computer Science 75 ( 2001 ), 97 -- 126 . E. Fischer, The art of uninformed decisions: A primer to propertytesting, The Computational Complexity Column of The Bulletin ofthe European Association for Theoretical Computer Science 75(2001), 97--126.","journal-title":"The Computational Complexity Column of The Bulletin ofthe European Association for Theoretical Computer Science"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_1_26_1","first-page":"37","article-title":"Hadwiger number for graphs with a givenmean degree of vertices","volume":"38","author":"Kostochka A.","year":"1982","unstructured":"A. Kostochka , The minimum Hadwiger number for graphs with a givenmean degree of vertices , Metody Diskret. Analliz. 38 ( 1982 ), 37 -- 58 {in Russion}. A. Kostochka, The minimum Hadwiger number for graphs with a givenmean degree of vertices, Metody Diskret. Analliz. 38 (1982), 37--58{in Russion}.","journal-title":"Metody Diskret. Analliz."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-15-1-271-283"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_1_31_1","first-page":"1","article-title":"Graph minor theory","volume":"43","author":"Lov\u00e1sz L.","year":"2006","unstructured":"L. Lov\u00e1sz , Graph minor theory , Bull. Amer. Math. Soc. 43 ( 2006 ),no. 1 , 75--86. L. Lov\u00e1sz, Graph minor theory, Bull. Amer. Math. Soc. 43 (2006),no. 1, 75--86.","journal-title":"Bull. Amer. Math. Soc."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_1_35_1","volume-title":"International Congress of Mathematicians.","author":"Rubinfeld R.","year":"2006","unstructured":"R. Rubinfeld , Sublinear time algorithms , in International Congress of Mathematicians. Vol. III ,1095--1110, Eur. Math. Soc., Z\u00fcrich , 2006 . R. Rubinfeld, Sublinear time algorithms, in International Congress of Mathematicians. Vol. III,1095--1110, Eur. Math. Soc., Z\u00fcrich, 2006."},{"volume-title":"Handbook of Randomized Computing,Vol. II","year":"2001","key":"e_1_3_2_1_36_1","unstructured":". Ron,Property testing , in: P. M. Pardalos, S. Rajasekaran, J. Reif andJ. D. P. Rolim, editors, Handbook of Randomized Computing,Vol. II , Kluwer Academic Publishers , 2001 , 597--649. . Ron,Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif andJ. D. P. Rolim, editors, Handbook of Randomized Computing,Vol. II, Kluwer Academic Publishers, 2001, 597--649."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_38_1","volume-title":"Graph sequences with hyperfinite limits are hyperfinite, ar Xiv:0711.3808","author":"Schramm O.","year":"2007","unstructured":"O. Schramm , Graph sequences with hyperfinite limits are hyperfinite, ar Xiv:0711.3808 , 2007 . O. Schramm, Graph sequences with hyperfinite limits are hyperfinite, ar Xiv:0711.3808, 2007."},{"volume-title":"Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas andD. Sotteau, eds.)","year":"1978","key":"e_1_3_2_1_39_1","unstructured":". Szemer\u00e9di,Regular partitions of graphs , In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas andD. Sotteau, eds.) , 1978 , 399--401. . Szemer\u00e9di,Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas andD. Sotteau, eds.), 1978, 399--401."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594196"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Victoria British Columbia Canada","acronym":"STOC '08"},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374433","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:49Z","timestamp":1750255069000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":42,"alternative-id":["10.1145\/1374376.1374433","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374433","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}