Algebraic property testing: the role of invariance

ABSTRACT

We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector space Kⁿ over a field K to a subfield F. We consider (F-)linear properties that are invariant under linear transformations of the domain and prove that an O(1)-local "characterization" is a necessary and sufficient condition for O(1)-local testability. when |K| = O(1). (A local characterization of a property is a definition of a property in terms of local constraints satisfied by functions exhibiting a property.) For the subclass of properties that are invariant under affine transformations of the domain, we prove that the existence of a single O(1)-local constraint implies O(1)-local testability. These results generalize and extend the class of algebraic properties, most notably linearity and low-degree-ness, that were previously known to be testable. In particular, the extensions include properties satisfied by functions of degree linear in n that turn out to be O(1)-locally testable. Our results are proved by introducing a new notion that we term "formal characterizations". Roughly this corresponds to characterizations that are given by a single local constraint and its permutations under linear transformations of the domain. Our main testing result shows that local formal characterizations essentially imply local testability. We then investigate properties that are linear-invariant and attempt to understand their local formal characterizability. Our results here give coarse upper and lower bounds on the locality of constraints and characterizations for linear-invariant properties in terms of some structural parameters of the property we introduce. The lower bounds rule out any characterization, while the upper bounds give formal characterizations. Combining the two gives a test for all linear-invariant properties with local characterizations. We believe that invariance of properties is a very interesting notion to study in the context of property testing in general and merits a systematic study. In particular, the class of linear-invariant and affine-invariant properties exhibits a rich variety among algebraic properties and offer better intuition about algebraic properties than the more limited class of low-degree functions.

REFERENCES

• 1: Noga Alon , Eldar Fischer , Ilan Newman , Asaf Shapira, A combinatorial characterization of the testable graph properties: it's all about regularity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132555]
• 2: N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing low-degree polynomials over GF(2). RANDOM 2003, pages 188--199.
• 3: Eli Ben-Sasson , Prahladh Harsha , Sofya Raskhodnikova, Some 3CNF properties are hard to test, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780594]
• 4: 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]
• 5: Andrej Bogdanov , Kenji Obata , Luca Trevisan, A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.93-102, November 16-19, 2002
• 6: Christian Borgs , Jennifer Chayes , László Lovász , Vera T. Sós , Balázs Szegedy , Katalin Vesztergombi, Graph limits and parameter testing, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132556]
• 7: S. D. Cohen. Functions and polynomials in vector spaces. Archiv der Mathematik, 48(5):409--419, May 1987.
• 8: P. Delsarte, J.M. Goethals, and F.J. MacWilliams. On generalized Reed-Muller codes and their relatives. Information and Control, 16(5):403--442, 1970.
• 9: A. M. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175--220, 1999.
• 10: 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]
• 11: O. Goldreich and O. Sheffet. On the randomness complexity of property testing. RANDOM 2007,pages 509--524.
• 12: Elena Grigorescu , Tali Kaufman , Madhu Sudan, 2-Transitivity Is Insufficient for Local Testability, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.259-267, June 22-26, 2008 [doi>10.1109/CCC.2008.31]
• 13: Charanjit S. Jutla , Anindya C. Patthak , Atri Rudra , David Zuckerman, Testing Low-Degree Polynomials over Prime Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.423-432, October 17-19, 2004 [doi>10.1109/FOCS.2004.64]
• 14: T. Kasami, S. Lin, and W. W. Peterson. New generalization of the Reed-Muller codes - Part I: Primitive codes. IEEE Trans. Inf. Th., 14:189--199, 1968.
• 15: Tali Kaufman , Simon Litsyn, Almost Orthogonal Linear Codes are Locally Testable, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.317-326, October 23-25, 2005 [doi>10.1109/SFCS.2005.16]
• 16: Tali Kaufman , Dana Ron, Testing Polynomials over General Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.413-422, October 17-19, 2004 [doi>10.1109/FOCS.2004.65]
• 17: T. Kaufman and M. Sudan. Algebraic property testing: the role of invariance. ECCC Technical Report, TR07-111, 2007.
• 18: Ronitt Rubinfeld, On the Robustness of Functional Equations, SIAM Journal on Computing, v.28 n.6, p.1972-1997, Dec. 1999 [doi>10.1137/S0097539796298625]
• 19: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
error-correcting codes, locally testable codes, sublinear time algorithms