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.