Abstract: As data sets become increasingly large, it becomes more and more impractical to analyze them in their entirety, whenever we want to extract small bits of information.  However, if we are clever about where we look, it turns out that we can obtain a surprising amount of information using only a *portion* of the input. Such algorithms, that selectively query the input, are called "sublinear time" algorithms. They provide fast, approximate answers, when access to the input is restricted or expensive. 

In this talk, we will see some example of sublinear time algorithms. In particular, we will look at "property testers," which are algorithms that check whether an input approximately has some property (for instance, whether a list of items is sorted). Property testing has been studied extensively and has many connections to learning theory and complexity theory.  I will aim to give a flavor of the mathematical techniques involved, and also discuss some more recent techniques for proving upper and lower bounds