Advanced Topics in Computer Science: Matrix Concentration and Applications

This course is about the applications of matrix or non-commutative concentration inequalities in theoretical computer science. We establish non-commutative Khintchine and the Chernoff bounds and then develop various applications, including undirected and directed graph sparsification, various rainbow girth problems in extremal combinatorics (e.g., the rainbow cycle conjecture and variants), and average-case analysis of algorithms, e.g., spectral clustering, connections to problems in discrepancy theory (e.g, the matrix Spencer conjecture and the Kadison Singer problem), and to free probability.