Research Abstracts - 2007

Goal

This work [3] aims on finding broad class of functions families that are locally testable. A family of functions is locally testable, if one can decide if a given function is in the family or is far from every function in the family by querying the input function in a constant number of locations. An obvious necessary condition for local testability of a family of functions, is having a local characterization, that is, a set of local constraints that define the family.

Our Results

This work shows that a local characterization is also a sufficient condition for local testability for family of functions that are invariant under linear transformations. This unifies the ``robustness'' results of prior works on linearity testing [4], low-degree testing [5], and testing of Reed-Muller codes [1,2].

This work also shows some function families (of high-degree polynomials) that possess very local characterizations, and hence are locally testable.

Last, we also investigate the general class of linear-invariant families and give a broad structural characterization for them. These turn into coarse bounds on their local characterizability. For instance we show that affine-invariant families possess a local characterization if and only if they possess a local constraint. This result provides support to the general conjecture of [1] that function families that are ``two-transitive'' and have a local constraint are locally testable.

References:

[1] N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron. Testing Low-Degree Polynomials over GF(2). In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2003), Lecture Notes in Computer Science, vol. 2764, pp. 188--199, Springer, New York, 2003.

[2] T. Kaufman and D. Ron. Testing Polynomials over General Fields. In Proceedings of the Forty-fifthth Annual Symposium on Foundations of Computer Science (FOCS 2004), pp. 413--422, 2004.

[3] Author T. Kaufman and Author M. Sudan. Algebraic Property Testing. Manuscript, 2006.

[4] M. Blum, M. Luby and R. Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. In Journal of Computer and System Sciences, volume 47, number 3, pp. 549--595, 1993.

[5] R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. In SIAM Journal on Computing, volume 25, number 2, pp. 252--271, April, 1996.