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

Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira

Research output: Contribution to journalArticle

75 Scopus citations

Abstract

A common thread in all of the 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 first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653-750] 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.

Original languageEnglish (US)
Pages (from-to)143-167
Number of pages25
JournalSIAM Journal on Computing
Volume39
Issue number1
DOIs
StatePublished - Jul 15 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Characterization
  • Property testing
  • Regularity lemma
  • Testable

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