Algebraic Property Testing

Abstract: A Property P of functions mapping from domain D to range R, is said to be testable if there exists a probabilistic algorithm that makes few (constant) queries for the value of f and accepts those satisfying P while rejecting functions that are far from any function satisfying P. Property testing emerged as a generalization of the ``linearity test'' of Blum, Luby and Rubinfeld. and plays a central role in the construction of probabilistically checkable proofs. One of the broad goals of research in ``Property Testing'' is to identify broad classes of functions that are testable. For instance Goldreich, Goldwasser and Ron initiated the study of graph properties that are testable; and the recent results of Alon and Shapira give very general classes of graph properties that are testable. In this work we return to expanding the scope of algebraic properties that are testable. We consider functions mapping a finite vector space K^n over a large field K to a subfield F of K. The class of properties we consider are those that are closed under linear-transformations. We show all such properties are testable, whenever they are characterized by local constraints. This unifies previous results in linearity testing, low-degree testing, testing of Reed-Muller codes, and testing of dual BCH codes. We also give some explanation of properties that are closed under linear and affine transformations. Joint work with Tali Kaufman (MIT).

Speaker's Bio: Madhu Sudan received his Bachelor's degree from the Indian Institute of Technology at New Delhi in 1987 and his Ph.D. from the University of California at Berkeley in 1992. From 1992-1997 he was a Research Staff Member at IBM's Thomas J. Watson Research Center. In 1997, he moved to MIT where he is now the Fujitsu Professor of Electrical Engineering and Computer Science. He was a Fellow at the Radcliffe Institute for Advanced Study from 2003-2004, and a Guggenheim Fellow from 2005-2006.

Madhu Sudan's research interests include computational complexity theory, algorithms and coding theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. He has served on numerous program committees for conferences in theoretical computer science, and was the program committee chair of the IEEE Conference on Computational Complexity '01, and the IEEE Symposium on Foundations of Computer Science '03. He is the chief editor of Foundations and Trends in Theoretical Computer Science, a new journal publishing surveys in the field. He is currently a member of the editorial boards of the Journal of the ACM and the SIAM Journal on Computing. Previously he served on the boards of the SIAM Journal on Discrete Mathematics, Information and Computation, and the IEEE Transactions on Information Theory. Madhu Sudan is a recipient of numerous awards including the ACM Doctoral Dissertation Award (1992), the IEEE Information Theory Society Paper Award (2000), the Godel Prize (2001) and the Nevanlinna Prize (2002).