Sublinear time algorithms
Ronitt Rubinfeld
Massachusetts Institute of Technology, Cambridge, USA
![Sublinear time algorithms cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fbooks%2Fcover-24.png&w=3840&q=90)
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.