Rubinfeld, Ronitt 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]. Cited in 14 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68W20 Randomized algorithms 68W25 Approximation algorithms Keywords:Sublinear time algorithms; property testing PDFBibTeX XMLCite \textit{R. Rubinfeld}, in: Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 22--30, 2006. Volume III: Invited lectures. Zürich: European Mathematical Society (EMS). 1095--1110 (2006; Zbl 1100.68041)