
Research
Abstracts  2007 
Algebraic Property TestingTali Kaufman & Madhu SudanGoalThis 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 ResultsThis 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], lowdegree testing [5], and testing of ReedMuller codes [1,2]. This work also shows some function families (of highdegree polynomials) that possess very local characterizations, and hence are locally testable. Last, we also investigate the general class of linearinvariant families and give a broad structural characterization for them. These turn into coarse bounds on their local characterizability. For instance we show that affineinvariant 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 ``twotransitive'' and have a local constraint are locally testable. References:[1] N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron. Testing LowDegree 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. 188199, Springer, New York, 2003. [2] T. Kaufman and D. Ron. Testing Polynomials over General Fields. In Proceedings of the Fortyfifthth Annual Symposium on Foundations of Computer Science (FOCS 2004), pp. 413422, 2004. [3] Author T. Kaufman and Author M. Sudan. Algebraic Property Testing. Manuscript, 2006. [4] M. Blum, M. Luby and R. Rubinfeld. SelfTesting/Correcting with Applications to Numerical Problems. In Journal of Computer and System Sciences, volume 47, number 3, pp. 549595, 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. 252271, April, 1996. 

