Testing of matrix properties
Eldar Fischer, Ilan Newman · 2001
Both collections above are variants of properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations (and some additional relations for the bipartite graph properties). 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=10) (for a small enough fixed ffl) 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. \\Lambda