Document Open Access Logo

Efficient Testing without Efficient Regularity

Authors Lior Gishboliner, Asaf Shapira

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.54.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Lior Gishboliner
Asaf Shapira

Cite As Get BibTex

Lior Gishboliner and Asaf Shapira. Efficient Testing without Efficient Regularity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.54

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.

Subject Classification

Keywords
  • Property testing
  • Induced C_4-freeness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon. Testing subgraphs in large graphs. Random Struct. Alg., 21:359-370, 2002. Google Scholar
  2. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451-476, 2000. Google Scholar
  3. N. Alon, E. Fischer, and I. Newman. Testing of bipartite graph properties. SIAM Journal on Computing, 37:959-976, 2007. Google Scholar
  4. N. Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: it’s all about regularity. SIAM Journal on Computing, 39:143-167, 2009. Google Scholar
  5. N. Alon and J. Fox. Easily testable graph properties. Combin. Probab. Comput., 24:646-657, 2015. Google Scholar
  6. N. Alon and A. Shapira. A characterization of easily testable induced subgraphs. Combin. Probab.Comput., 15:791-805, 2006. Google Scholar
  7. N. Alon and A. Shapira. A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing, 37:1703-1727, 2008. Google Scholar
  8. L. Avigad and O. Goldreich. Testing graph blow-up. In Proc. of APPROX-RANDOM, pages 389-399. Springer, 2011. Google Scholar
  9. D. Conlon and J. Fox. Bounds for graph regularity and removal lemmas. GAFA, 22:1191-1256, 2012. Google Scholar
  10. D. Conlon and J. Fox. Graph removal lemmas. Surveys in Combinatorics, pages 1-50, 2013. Google Scholar
  11. P. Erdős. On extremal problems of graphs and generalized graphs. Israel J. Math, 2:183-190, 1964. Google Scholar
  12. P. Erdős. On some problems in graph theory, combinatorial analysis and combinatorial number theory. Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, pages 1-17, 1984. Google Scholar
  13. J. Fox. A new proof of the graph removal lemma. Ann. of Math., 174:561-579, 2011. Google Scholar
  14. L. Gishboliner and A. Shapira. Removal lemmas with polynomial bounds. Proc. of STOC, pages 510-522, 2017. Google Scholar
  15. O. Goldreich. Introduction to property testing, Forthcoming book, 2017. Google Scholar
  16. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. J. ACM, 45:653-750, 1998. Google Scholar
  17. O. Goldreich and D. Ron. On proximity-oblivious testing. SIAM J. on Computing, 40:534-566, 2011. Google Scholar
  18. T. Gowers. Lower bounds of tower type for szemerédi’s uniformity lemma. GAFA, 7:322-337, 1997. Google Scholar
  19. A. Gyárfás, A. Hubenko, and J. Solymosi. Large cliques in c₄-free graphs. Combinatorica, 22:269-274, 2002. Google Scholar
  20. L. Lovász. Large networks and graph limits, volume 60. American Mathematical Society Providence, 2012. Google Scholar
  21. G. Moshkovitz and A. Shapira. A sparse regular aproximation lemma. Google Scholar
  22. V. Rödl and R. Duke. On graphs with small subgraphs of large chromatic number. Graphs and Combinatorics, 1:91-96, 1985. Google Scholar
  23. R. Rubinfeld and M. Sudan. Robust charachterization of polynomials with applications to program testing. SIAM Journal on Computing, 25:252-271, 1996. Google Scholar
  24. I.Z. Ruzsa and E. Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18:939-945, 1976. Google Scholar
  25. E. Szemerédi. Regular partitions of graphs. In: Proc. Colloque Inter. CNRS, %(J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds., pages 399-401, 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact