CSAIL Publications and Digital Archive header
bullet Research Abstracts Home bullet CSAIL Digital Archive bullet Research Activities bullet CSAIL Home bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line


Research Abstracts - 2007
horizontal line

horizontal line

vertical line
vertical line

Algebraic Property Testing

Tali Kaufman & Madhu Sudan


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.


[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.


vertical line
vertical line
horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu