A combinatorial characterization of the testable graph properties: It's all about regularity

Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

79 Scopus citations

Abstract

A common thread in recent results concerning the testing of dense graphs is the use of Szemeré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é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édi-partitions. This means that in some sense, testing for Szemeré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.

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
Pages251-260
Number of pages10
StatePublished - Sep 5 2006
Externally publishedYes
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
CountryUnited States
CitySeattle, WA
Period5/21/065/23/06

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Characterization
  • Property Testing
  • Regularity Lemma

Fingerprint Dive into the research topics of 'A combinatorial characterization of the testable graph properties: It's all about regularity'. Together they form a unique fingerprint.

Cite this