Alon, Noga ;
BenEliezer, Omri
Efficient Removal Lemmas for Matrices
Abstract
The authors and Fischer recently proved that any hereditary property of twodimensional 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 constantsize 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 epsilonfraction of the entries of a binary matrix M can be covered by pairwisedisjoint copies of some (s x t) matrix A, then a deltafraction 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 BenEliezer},
title = {{Efficient Removal Lemmas for Matrices}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {25:125:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7574},
URN = {urn:nbn:de:0030drops75744},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.25},
annote = {Keywords: Property Testing, Removal Lemma, Matrix Regularity Lemma, Binary Matrix}
}
11.08.2017
Keywords: 

Property Testing, Removal Lemma, Matrix Regularity Lemma, Binary Matrix 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 