License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.54
URN: urn:nbn:de:0030-drops-83124
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8312/
Go to the corresponding LIPIcs Volume Portal

Gishboliner, Lior ; Shapira, Asaf

Efficient Testing without Efficient Regularity

pdf-format:
LIPIcs-ITCS-2018-54.pdf (0.5 MB)

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 tower-type 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_4-free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of tower-type 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:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8312},
  URN =		{urn:nbn:de:0030-drops-83124},
  doi =		{10.4230/LIPIcs.ITCS.2018.54},
  annote =	{Keywords: Property testing, Induced C_4-freeness}
}

Keywords: Property testing, Induced C_4-freeness
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI