Sublinear Time Algorithms
Ronitt Rubinfeld, A. Shapira · SIAM Journal on Discrete Mathematics · 2011
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 types of answers that one can hope to achieve in this setting.