UTCS Colloquium and ACT Seminar: Madhu Sudan/MIT "The Role of Invariance in Property Testing" ACES 2.402, Friday, May 1, 2009 11:00 a.m.
Type of Talk: UTCS Colloquium and ACT Seminar
peaker/Affiliation: Madhu Sudan/ MIT
, May 1, 2009 11:00 a.m.
Location: ACES 2.402
st: David Zuckerman
Talk Title: "The Role of Inva
riance in Property Testing"
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.
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
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,
Based on joint works with Elena Grigorescu
and Tali Kaufman (MIT).
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.
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).
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Portfolio Program in Robotics
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct