CS 7880 - Husker Northeastern

This class will meet in WVH 366.

Course overview: The emergence of massive datasets has motivated a rapidly growing interest in algorithms that can process huge amounts of data.

When working with such massive inputs, inherent assumptions of traditional algorithms (such as the possibility of reading or storing the whole input with a single machine) no longer hold.

We thus need a new paradigm for the design and analysis of algorithms.

This is precisely the focus of sublinear algorithms.

In this course, we will study various algorithms whose time, space, or communication are much smaller than the input size.

Problems that we study will include maximum matchings, graph connectivity, minimum spanning trees, frequency estimation, independent sets, graph coloring, and clustering.

We study these problems across various models of sublinear algorithms, including sublinear time algorithms, streaming algorithms, and massively parallel computation (MPC).

Topics (tentative list): • Basic probabilistic tools • Sublinear time algorithms for average degree and connected components • Sublinear time algorithms for maximal independent set and maximum matching via randomized greedy • Streaming algorithms: frequency moments estimation • Streaming lower bounds via communication complexity • Massively parallel computation (MPC): introduction, space-regimes, and simple tools • MPC algorithms for maximum matching • MPC algorithms for graph connectivity and minimum spanning trees • AGM linear sketching • Sublinear algorithms for graph coloring • Sublinear algorithms for cut problems • Sublinear algorithms for clustering problems

CS 7880: SpTp: Sublinear Algorithm

Spring 2023 Semester

Fall 2022 Semester