Testing of matrix properties

ABSTRACT

Combinatorial property testing 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 (&egr;,q)-test for P is a randomized algorithm that queries at most q places of an input x and distinguishes with probability 2/3 between the case that f has the property and the case that at least an &egr;-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 is an (&egr,poly(1/&egr))-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 and many other properties. A (less efficient) test for such properties with larger fixed size alphabets is also presented. Another result is a more efficient test than was previously known for a collection of bipartite graph properties.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}) exists. The above results identify new classes of efficiently

REFERENCES

• 1: N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs. Combinatorica 20: 451-476, 2000.
• 2: Noga Alon , Michael Krivelevich , Ilan Newman , Mario Szegedy, Regular Languages are Testable with a Constant Number of Queries, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.645, October 17-18, 1999
• 3: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 4: Tugkan Batu , Ronitt Rubinfeld , Patrick White, Fast Approximate PCPs for Multidimensional Bin-Packing Problems, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.245-256, August 08-11, 1999
• 5: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 6: Yevgeniy Dodis , Oded Goldreich , Eric Lehman , Sofya Raskhodnikova , Dana Ron , Alex Samorodnitsky, Improved Testing Algorithms for Monotonicity, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.97-108, August 08-11, 1999
• 7: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 8: E. Fischer, On the strength of comparisons in property testing, manuscript.
• 9: Eldar Fischer, Testing graphs for colorable properties, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.873-882, January 07-09, 2001, Washington, D.C., United States
• 10: Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
• 11: T. K.ovary, V.T. Sos, and P. Turan, On a problem of K. Zarankiewicz, Colloq. Math., 3:50-57, 1954.
• 12: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 13: Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
• 14: I. Newman, Testing of function that have small width branching programs, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.251, November 12-14, 2000
• 15: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 16: A. C. Yao, Probabilistic computation, towards a unified measure of complexity. In18th IEEE FOCS Conference Proceedings, pages 222-227, 1977.
• 17: K. Zarankiewicz, Problem P 101. Colloq. Math., 2:116-131, 1951.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Reliability, Theory, Verification

Keywords:
matrix properties, property testing