Abstract
The regularity lemma of Szemeredi turned out to be the most powerful tool for studying the testability of graph properties in the dense graph model. In fact, as we argue in this paper, this lemma can be used in order to prove (essentially) all the previous results in this area. More precisely, a barrier for obtaining an efficient testing algorithm for a graph property P was having an efficient regularity lemma for graphs satisfying P. The problem is that for many natural graph properties (e.g. triangle freeness) it is known that a graph can satisfy P and still only have regular partitions of towertype size. This means that there was no viable path for obtaining reasonable bounds on the query complexity of testing such properties.
In this paper we consider the property of being induced C_4free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of towertype size.
By developing a new approach for this problem we manage to overcome this barrier and thus obtain a merely exponential bound for testing this property. This is the first substantial progress on a problem raised by Alon in 2001, and more recently by Alon, Conlon and Fox.
We thus obtain the first example of an efficient testing algorithm that cannot be derived from an efficient version of the regularity lemma.
BibTeX  Entry
@InProceedings{gishboliner_et_al:LIPIcs:2018:8312,
author = {Lior Gishboliner and Asaf Shapira},
title = {{Efficient Testing without Efficient Regularity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {54:154:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8312},
URN = {urn:nbn:de:0030drops83124},
doi = {10.4230/LIPIcs.ITCS.2018.54},
annote = {Keywords: Property testing, Induced C_4freeness}
}
Keywords: 

Property testing, Induced C_4freeness 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 
Issue Date: 

2018 
Date of publication: 

05.01.2018 