ABSTRACT
What computational problems can we solve when we only have time to look at a tiny fraction of the data? This general question has been studied from many different angles in statistics. More recently, with the recent proliferation of massive datasets, it has also become a central question in computer science as well. Essentially, all of the research on this question starts with a simple observation: Except for a very small number of special cases, the only problems that can be solved in this very restrictive setting are those that admit approximate solutions.
