Sub-linear time algebraic algorithms
Lecturer: Prof. Madhu Sudan (MIT, USA).
About the lecturer | Course Summary | Scribe notes | Assignment
About the lecturer:
Madhu Sudan, born in Madras (India), 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. He is currently the Fujitsu
Professor of Electrical Engineering and Computer Science at the Massachussetts Institute
of Technology, Cambridge, USA.
His work on probabilistically checkable proofs was a landmark contribution
to computational complexity theory, establishing one of the most eminent results in computer
science (PCP theorem), and a new technique of proving hardness of approximation problems.
He also contributed to algorithmic coding theory by the work on list-decoding algorithms for
error-correcting codes. He was awarded the Rolf Nevanlinna Prize at the 24th International Congress
of Mathematicians in 2002. He also received the ACM's Distinguished Doctoral Dissertation Award
in 1993, and the Gödel Prize in 2001.
Course summary:
A modern thrust in computing is to design algorithms that
take vast amounts of data and try to estimate properties
of the data in a "quick and dirty" way. Sub-linear time
algorithms is the area of theoretical computer science
which presents design and rigorous analysis of such
algorithms. The study of sublinear time algorithms started
with the seminal work of Blum, Luby, and Rubinfeld (1990)
who presented a "constant-time" algorithm to test if a function
mapping a finite group to a finite group is essentially a
homomorphism between the groups. This algorithm has since become
quite famous as the "linearity test". The linearity test,
and follow-up works, including "low-degree tests" (tests
that check if a given multivariate function is essentially a
low-degree polynomial) have become central elements in
modern computational complexity (and form the heart of
constructions of probabilistically checkable proofs (PCPs)).
In this series of lectures we will describe the model of
sublinear-time algorithms and present the (extremely simple)
algorithms for linearity testing and low-degree testing.
We will then describe some of analysis which draw upon
algebra, geometry, analysis.
Scribe notes (The notes are not yet approved by Madhu Sudan).
Assignment: [PDF]
due Sun, November 4.
Please send your solutions in PDF by e-mail to madhu AT mit DOT edu.