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.
The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property testing. Our main result in this paper is a solution of an important special case of this general problem: Call a property tester oblivious if its decisions are independent of the size of the input graph. We show that a graph property @math has an oblivious one-sided error tester if and only if @math is semihereditary. We stress that any “natural” property that can be tested (either with one-sided or with two-sided error) can be tested by an oblivious tester. In particular, all the testers studied thus far in the literature were oblivious. Our main result can thus be considered as a precise characterization of the natural graph properties, which are testable with one-sided error. One of the main technical contributions of this paper is in showing that any hereditary graph property can be tested with one-sided error. This general result contains as a special case all the previous results about testing graph properties with one-sided error. More importantly, as a special case of our main result, we infer that some of the most well-studied graph properties, both in graph theory and computer science, are testable with one-sided error. Some of these properties are the well-known graph properties of being perfect, chordal, interval, comparability, permutation, and more. None of these properties was previously known to be testable.