CS-448 Sublinear Algorithms for Big Data Analysis

Credits: 4
Lecturer: Michael Kapralov
Email: michael.kapralov@epfl.ch
Office: INJ113
Office hours: Wednesdays 14.00-15.00
TA: Amir Zandieh
Email: amir.zandieh@epfl.ch
Office hours: Mondays 9.00-10.00 in INJ114
Schedule: Wednesdays 10-13 in INM10

Short description: As the sizes of modern datasets grow, many classical polynomial time, and sometimes even linear time, algorithms become prohibitively expensive: the input is often too large to be stored in the memory of a single compute node, is hard to partition among nodes in a cluster to avoid communication bottlenecks, or is very expensive to acquire in the first place. Thus, processing of such datasets requires a new set of algorithmic tools for computing with extremely constrained resources. This course is about sublinear algorithms , i.e. algorithms whose resource requirements are substantially smaller than the size of the input that they operate on. We will define rigorous mathematical models for computing with constrained resources, cover main algorithmic techniques that have been developed for sublinear data processing, as well as discuss limitations inherent to computing with constrained resources.

List of topics (tentative):

Prerequisites: Bachelor courses on algorithms, complexity theory, and discrete mathematics; mathematical maturity.

Grading: The grade will be based on problem sets (50%) and a final (50%).

For more details see the official course book here.