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 @math , any hereditary property @math of matrices over @math , and any @math , there exists @math such that for any matrix @math over @math that is @math -far from satisfying @math , most of the @math submatrices of @math do not satisfy @math . Here being @math -far from @math means that one needs to modify at least an @math -fraction of the entries of @math to make it satisfy @math . However, in the above general removal lemma, @math grows very fast as a function of @math , even when @math 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 @math binary matrix @math and any @math there exists @math polynomial in @math , such that for any binary matrix @math in which less than a @math -fraction of the @math submatrices are equal to @math , there exists a set of less than an @math -fraction of the entries of @math that intersects every @math -copy in @math . 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.
We finish by mentioning several other relevant removal lemma type results. Removal lemmas for vectors (i.e. @ one dimensional matrices where the order is important) are generally easier to obtain; in particular, a removal lemma for vectors over a fixed finite alphabet can be derived from a removal lemma for regular languages proved in @cite_13 . A removal lemma for partially ordered sets with a grid-like structure, which can be seen as a generalization of the removal lemma for vectors, can be deduced from a result of Fischer and Newman in @cite_23 , where they mention that this problem for submatrices is more complicated and not understood. Recently, Ben-Eliezer, Korman and Reichman @cite_19 obtained a removal lemma for patterns in multi-dimensional matrices. A pattern must be taken from locations, whereas in our case the rows and columns of a submatrix need not be consecutive. The case of patterns behaves very differently than that of submatrices, and in particular, in the removal lemma for patterns the parameters are linearly related (for any alphabet size) unlike the case of submatrices (in which, for alphabets of @math letters or more, the relation cannot be polynomial).
@cite_19 @cite_13 @cite_23
2609757535 2036501955 2091126969
Understanding the local behaviour of structured multi-dimensional data is a fundamental problem in various areas of computer science. As the amount of data is often huge, it is desirable to obtain sublinear time algorithms, and specifically property testers, to understand local properties of the data. We focus on the natural local problem of testing pattern freeness: given a large @math -dimensional array @math and a fixed @math -dimensional pattern @math over a finite alphabet, we say that @math is @math -free if it does not contain a copy of the forbidden pattern @math as a consecutive subarray. The distance of @math to @math -freeness is the fraction of entries of @math that need to be modified to make it @math -free. For any @math and any large enough pattern @math over any alphabet, other than a very small set of exceptional patterns, we design a tolerant tester that distinguishes between the case that the distance is at least @math and the case that it is at most @math , with query complexity and running time @math , where @math and @math depend only on @math . To analyze the testers we establish several combinatorial results, including the following @math -dimensional modification lemma, which might be of independent interest: for any large enough pattern @math over any alphabet (excluding a small set of exceptional patterns for the binary case), and any array @math containing a copy of @math , one can delete this copy by modifying one of its locations without creating new @math -copies in @math . Our results address an open question of Fischer and Newman, who asked whether there exist efficient testers for properties related to tight substructures in multi-dimensional structured data. They serve as a first step towards a general understanding of local properties of multi-dimensional arrays, as any such property can be characterized by a fixed family of forbidden patterns. We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language @math and an integer n there exists a randomized algorithm which always accepts a word w of length n if @math and rejects it with high probability if @math has to be modified in at least @math positions to create a word in L. The algorithm queries @math bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in @math . We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of @math . The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means. Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (e, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2 3 between the case that f has the property and the case that at least an e-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (e, poly(1 e))-test for every property of 0 1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n 1 4) (for a small enough fixed e) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results.