CS 7880: SpTp: Sublinear Algorithm
Lecture - 4 credits
- 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
This class will meet in WVH 366. Show more.