Document Open Access Logo

Efficient Removal Lemmas for Matrices

Authors Noga Alon, Omri Ben-Eliezer

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.25.pdf
  • Filesize: 0.48 MB
  • 18 pages

Document Identifiers

Author Details

Noga Alon
Omri Ben-Eliezer

Cite As Get BibTex

Noga Alon and Omri Ben-Eliezer. Efficient Removal Lemmas for Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.25

Abstract

The authors and Fischer recently proved that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing an (ordered) matrix removal lemma, which states the following: If a matrix is far from satisfying some hereditary property, then a large enough constant-size random submatrix of it does not satisfy the property with probability at least 9/10. Here being far from the property means that one needs to modify a constant fraction of the entries of the matrix to make it satisfy the property.

However, in the above general removal lemma, the required size of the random submatrix grows very fast as a function of the distance of the matrix from satisfying the property. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: If an epsilon-fraction of the entries of a binary matrix M can be covered by pairwise-disjoint copies of some (s x t) matrix A, then a delta-fraction of the (s x t)-submatrices of M are equal to A, where delta is polynomial in epsilon.

We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas.

Subject Classification

Keywords
  • Property Testing
  • Removal Lemma
  • Matrix Regularity Lemma
  • Binary Matrix

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 Structures and Algorithms, 21:359-370, 2002. Google Scholar
  2. N. Alon, O. Ben-Eliezer, and E. Fischer. Testing hereditary properties of ordered graphs and matrices. arXiv, 1704:02367, 2017. Google Scholar
  3. N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster. The algorithmic aspects of the regularity lemma. Journal of Algorithms, 16:80-109, 1994. Google Scholar
  4. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451-476, 2000. Google Scholar
  5. N. Alon, E. Fischer, and I. Newman. Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM J. Comput., 37:959-976, 2007. Google Scholar
  6. N. Alon and J. Fox. Easily testable graph properties. Combin. Probab. Comput, 24:646-657, 2015. Google Scholar
  7. N. Alon, M. Krivelevich, I. Newman, and M. Szegedy. Regular languages are testable with a constant number of queries. SIAM J. Comput., 30:1842-1862, 2001. Google Scholar
  8. N. Alon and A. Shapira. A characterization of easily testable induced subgraphs. Combin. Probab. Comput., 15:791-805, 2006. Google Scholar
  9. N. Alon and A. Shapira. A characterization of easily testable induced subgraphs. SIAM J. Comput., 37:1703-1727, 2008. Google Scholar
  10. F. Behrend. On sets of integers which contain no three terms in arithmetic progression. Proc. Nat. Acad. Sci., 32:331-332, 1946. Google Scholar
  11. O. Ben-Eliezer, S. Korman, and D. Reichman. Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.9.
  12. D. Conlon and J. Fox. Bounds for graph regularity and removal lemmas. Geom. Funct. Anal., 22:1191-1256, 2012. Google Scholar
  13. D. Conlon and J. Fox. Graph removal lemmas. In Surveys in Combinatorics, pages 1-49. Cambridge Univ. Press, 2013. Google Scholar
  14. E. Fischer and I. Newman. Testing of matrix-poset properties. Combinatorica, 27:293-327, 2007. Google Scholar
  15. E. Fischer and E. Rozenberg. Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects. In Proc. 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, pages 464-478. Springer Berlin, Heidelberg, 2007. Google Scholar
  16. J. Fox. A new proof of the graph removal lemma. Ann. of Math., 174:561-579, 2011. Google Scholar
  17. L. Gishboliner and A. Shapira. Removal lemmas with polynomial bounds. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 510-522. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055404.
  18. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. J. ACM, 45:653-750, 1998. Google Scholar
  19. T. Gowers. A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 11:465-588, 2001. Google Scholar
  20. L. Lovász and B. Szegedy. Regularity partitions and the topology of graphons. In An irregular mind, pages 415-445. János Bolyai Math. Soc., Budapest, 2010. Google Scholar
  21. B. Nagle, V. Rődl, and M. Schacht. The counting lemma for regular k-uniform hypergraphs. Random Structures and Algorithms, 28:113-179, 2006. Google Scholar
  22. V. Rödl and J. Skokan. Regularity lemma for uniform hypergraphs. Random Structures and Algorithms, 25:1-42, 2004. Google Scholar
  23. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. Siam J. Comput., 25:252-271, 1996. Google Scholar
  24. I. Z. Ruzsa and E. Szemerédi. Triple systems with no six points carrying three triangles. In Combinatorics, Vol. II, pages 939-945. Coll. Math. Soc. J. Bolyai 18, North-Holland, Amsterdam-New York, 1978. Google Scholar
  25. M. Sudan. Invariance in property testing. In Property Testing: Current Research and Surveys, pages 211-227. Springer Brelin, Heidelberg, 2010. Google Scholar
  26. E. Szemerédi. Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, pages 399-401. Colloq. Internat. CNRS 260, Orsay, 1976. Google Scholar
  27. T. Tao. A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A, 113:1257-1280, 2006. 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