Sub-linear time algebraic algorithms

Speaker(s)

Madhu Sudan

Affiliation

Massachusetts Institute of Technology

Date

Oct. 4, 2007, 4:15 p.m.

Room

room 4420

Seminar

Seminar Algorithms

---

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.

---