TuTh -- 3:05-4:25: CCB 53
Instructor: Richard Peng
Sampling, or picking a subset of the data, is a process central to statistics and randomization. Recent algorithmic frameworks relying on sampling graphs and matrices highlighted several connections between combinatorial, randomized, and optimization algorithms. This course aims to discuss some of these connections, as well as explore sampling based algorithms in these multiple contexts. The exact choice of topics will depend on student interest. A tentative and probably overly ambitious list of topics include:
- Parallel computing: maximal independent set, tree contraction, low diameter decompositions, and approximating graphs with trees.
- Graph algorithms: graph sparsification and its algorithmic consequences for flows/cuts/trees.
- Randomized numerical linear algebra: reducing big data to small data, with a focus on regression and low-rank approximations of matrices.
- Spectral graph theory: the interplay between graphs, matrices, and electricity, leading to random walks, expanders, and heat kernels.
- Iterative methods: solving a linear system via solving several similar ones, or many easy ones. Connection with (stochastic) optimization will also be discussed.
