## 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 language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017 |

Editors | Jose D. P. Rolim, Klaus Jansen, David P. Williamson, Santosh S. Vempala |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770446 |

DOIs | |

State | Published - Aug 1 2017 |

Externally published | Yes |

Event | 20th 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 2017 → Aug 18 2017 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 81 |

ISSN (Print) | 1868-8969 |

### Other

Other | 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017 |
---|---|

Country/Territory | United States |

City | Berkeley |

Period | 8/16/17 → 8/18/17 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Binary Matrix
- Matrix Regularity Lemma
- Property Testing
- Removal Lemma