A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

Speaker  Asaf Shapira

Host  Jennifer Chayes/Christian Borgs

Affiliation  Tel Aviv University

Duration  01:06:52

Date recorded  27 January 2006

A common thread in all the recent results concerning testing 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 Szemeredi- 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 Szemeredi-partitions. This means that in some sense, testing for Szemeredi-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 in the 1996 paper of Goldreich, Goldwasser and Ron that initiated the study of graph property-testing.This characterization also gives an intuitive explanation as to what makes a graph property testable.

Joint work with N. Alon, E. Fischer and I. Newman.

©2006 Microsoft Corporation. All rights reserved.
> A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity