Type of Talk:  UTCS Colloquium and ACT Seminar

S

peaker/Affiliation:  Madhu Sudan/ MIT

Date/Time:  Friday

, May 1, 2009  11:00 a.m.

Location:  ACES 2.402

Ho

st:  David Zuckerman

Talk Title:  "The Role of Inva

riance in Property Testing"

Talk Abstract:

Property testi

ng considers the task of testing if some given data satisfies a desired pro

perty by sampling the data probabilistically in very few places. The ``olde

st'''' property test might be the use of polling to predict the outcome of

an upcoming election. Modern research has extended the scope of property te

sts to a much richer class of properties including tests of linearity (&quo

t;is the data essentially linear with respect to some parameters"),
multilinearity, low-degreeness, colorability ("is the data describ

ing a graph with small chromatic number") etc.

What makes

some properties testable so efficiently, that we do not have to look at th

e entire data in order to test for it? We suggest that for interesting prop

erties, testability ought to be related to the "invariances" s

hown by the property: i.e., if the data is viewed as a function from some

input to some output, then the "invariances" are given by a se

t (a group) of permutations of the input space under which the property is

invariant. We then investigate this hypothesis in the context of "alg

ebraic properties".

The class of algebraic properties we c

onsider are linear properties (if f, g satisfy the property, then so does
f+g) mapping a vector space K^n over a field K to a subfield F.  The
invariance we study is that of "linear-invariance" (the proper

ty is invariant under linear transformations of the domain).  Linear

invariant properties lead to broad extensions of the algebraic properties o

f linearity and low-degreeness. We show that when $K= O(1)$, linear-invari

ant properties are testable with constant queries if and only if they posse

ss O(1)-local characterizations.  This leads to a unifying proof of p

revious algebraic property tests (though not in their most "efficient

" forms) while leading to many new properties that were not known to

be testable before. In the talk, we will attempt to highlight some of the

interesting aspects of linear-invariant properties, and describe our new,
unifying, analysis.

Based on joint works with Elena Grigorescu
and Tali Kaufman (MIT).

Speaker Bio:

Madhu  Sudan 
received  his  Bachelor''s  degree  from  th

e 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 wa

s a Research Staff Member at IBM''s Thomas J. Watson Research Center. In 19

97, he moved to MIT where he is now the Fujitsu Professor of Electrical En

gineering and Computer Science, and Associate Director of MIT''s CSAIL (Co

mputer Science and Artificial Intelligence Laboratory.

Madhu Su

dan''s research interests include computational complexity theory, algorit

hms, and coding theory.  He is best known for his works on probabili

stic checking  of proofs, and on the design of list-decoding algorit

hms for error-correcting codes.

In 2002, Madhu Sudan was awarde

d the Nevanlinna Prize, for outstanding contributions to the mathematics o

f computer science, at the International Congress of Mathematicians in Bei

jing. Madhu Sudan''s other awards include the ACM Doctoral Dissertation Awa

rd (1992), the IEEE Information Theory Society Paper Award (2000) and the

Godel Prize (2001), Distinguished Alumnus Award of the University of Calif

ornia at Berkeley (2003), and Distinguished Alumnus Award of the Indian In

stitute of Technology at Delhi (2004). Madhu Sudan is a Guggenheim Fellow (

inducted 2005) and an ACM Fellow (inducted 2008).