Sub-linear time algebraic algorithms
- Prelegent(ci)
- Madhu Sudan
- Afiliacja
- Massachusetts Institute of Technology
- Termin
- 4 października 2007 16:15
- Pokój
- p. 4420
- Seminarium
- Seminarium "Algorytmika"
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.