Sublinear Algorithms for Big Data

Catalog description

A huge quantity of data is worth little unless we can extract insights from it. Yet, the large quantities mean that classic algorithms (running in linear, quadratic or even more time) can be infeasible in practice. We must instead turn to new algorithmic approaches and paradigms, which allow us to answer valuable questions about our data in runtime that is still feasible even when the data set is Facebook-sized. Surprisingly, to answer many computational and statistical questions, sometimes there is no need to read/store every piece of data! This course focuses on this exciting "sublinear" algorithmic regime. We will study practical algorithms, making clever use of randomness with strong theoretical guarantees Prerequisites: (CS22 or equivalent); (CS145 or APMA1650/1655 or equivalent); (CS157 or CS155). Mathematical maturity is essential: this is a theory course with proofs. Recommended: CS155