×

Sublinear time algorithms. (English) Zbl 1100.68041

Sanz-Solé, Marta (ed.) et al., Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Volume III: Invited lectures. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-022-7/hbk). 1095-1110 (2006).
Summary: Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the sorts of answers that one might be able to achieve in this new setting.
For the entire collection see [Zbl 1095.00006].

MSC:

68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite