@inproceedings{2a9cdba4889149f2a8393f27515c5a36,

title = "A combinatorial characterization of the testable graph properties: It's all about regularity",

abstract = "A common thread in recent results concerning the testing of dense graphs is the use of Szemer{\'e}di'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{\'e}di-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 P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemer{\'e}di-partitions. This means that in some sense, testing for Szemer{\'e}di-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 raised in the 1996 paper of Goldreich, Goldwasser and Ron [25] that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.",

keywords = "Characterization, Property Testing, Regularity Lemma",

author = "Noga Alon and Eldar Fischer and Ilan Newman and Asaf Shapira",

year = "2006",

month = sep,

day = "5",

language = "English (US)",

isbn = "1595931341",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "251--260",

booktitle = "STOC'06",

note = "38th Annual ACM Symposium on Theory of Computing, STOC'06 ; Conference date: 21-05-2006 Through 23-05-2006",

}