Efficient removal lemmas for matrices

Noga Alon, Omri Ben-Eliezer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 the following (ordered) matrix removal lemma: For any finite alphabet Σ, any hereditary property P of matrices over Σ, and any ϵ > 0, there exists fP(ϵ) such that for any matrix M over Σ that is ϵ-far from satisfying P, most of the fP(ϵ) × fP(ϵ) submatrices of M do not satisfy P. Here being ϵ-far from P means that one needs to modify at least an ϵ-fraction of the entries of M to make it satisfy P. However, in the above general removal lemma, fP(ϵ) grows very fast as a function of ϵ-1, even when P is characterized by a single forbidden submatrix. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: For any fixed s×t binary matrix A and any ϵ > 0 there exists δ > 0 polynomial in ϵ, such that for any binary matrix M in which less than a δ-fraction of the s×t submatrices are equal to A, there exists a set of less than an ϵ-fraction of the entries of M that intersects every A-copy in M. 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017
EditorsJose D. P. Rolim, Klaus Jansen, David P. Williamson, Santosh S. Vempala
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770446
DOIs
StatePublished - Aug 1 2017
Externally publishedYes
Event20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017 - Berkeley, United States
Duration: Aug 16 2017Aug 18 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume81
ISSN (Print)1868-8969

Other

Other20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017
CountryUnited States
CityBerkeley
Period8/16/178/18/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

Fingerprint Dive into the research topics of 'Efficient removal lemmas for matrices'. Together they form a unique fingerprint.

Cite this