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.APPROX-RANDOM.2017.25
URN: urn:nbn:de:0030-drops-75744
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7574/
Go to the corresponding LIPIcs Volume Portal

Alon, Noga ; Ben-Eliezer, Omri

Efficient Removal Lemmas for Matrices

pdf-format:
LIPIcs-APPROX-RANDOM-2017-25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{alon_et_al:LIPIcs:2017:7574,
  author =	{Noga Alon and Omri Ben-Eliezer},
  title =	{{Efficient Removal Lemmas for Matrices}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7574},
  URN =		{urn:nbn:de:0030-drops-75744},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.25},
  annote =	{Keywords: Property Testing, Removal Lemma, Matrix Regularity Lemma, Binary Matrix}
}

Keywords: Property Testing, Removal Lemma, Matrix Regularity Lemma, Binary Matrix
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

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