Sublinear time algorithms

  • Ronitt Rubinfeld

    Massachusetts Institute of Technology, Cambridge, USA
Sublinear time algorithms cover
Download Chapter PDF

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.