Sublinear time algorithms
Ronitt Rubinfeld
Massachusetts Institute of Technology, Cambridge, USA
A subscription is required to access this book chapter.
Abstract
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.