Linear algebraic tools in TCS (CS698B)

Course description:

Linear algebra has played a very crucial role in the development of many scientific and engineering fields. In particular, linear algebraic techniques have various applications in combinatorics, linear algebra and theoretical computer science. An excellent survey on linear algebraic techniques in combinatorics by Babai and Frankl can be found here .

The course will focus on two linear algebraic tools, convex optimization and spectral graph theory, which have played an important role in the development of theoretical computer science.

The first tool will be convex optimization and its applications in the field of complexity theory. Initially, we will look at linear programming. Through linear programming, we will introduce the concepts of convexity, optimization and duality. We will move to semidefinite programming later and generalize the concepts studied before. Along the way, we will show applications of convex programming in finding cuts and flows. This part will introduce them to the concepts of relaxation and rounding.

The second tool will talk about spectral graph theory. We will study graphs by looking at the spectrum of the associated matrices. It is surprising that many of the combinatorial properties of the graph can be studied by looking at the eigenvalues and eigenvectors of the Laplacian matrix of the graph. We will discuss random walks, expanders and approximate solutions to linear equations.

Notes

Topic Link
Introduction to the course Introduction
Basics of linear algebra Linear algebra
Introduction to linear programming Linear programming
Affine and convex sets Convex sets
Hyperplane separation and Duality Duality
Primal dual method and its application to max flow Primal dual
Spectral decomposition, positive semidefinite matrices and its cone Positive semidefinite matrices
Semidefinite programming SDP
Dual cones, dual of cone programs SDP dual
Approximation algorithm for max cut Goemans Williamson
Introduction to spectral graph theory Introduction to SGT
Bipartite graphs, coloring and highest eigenvalue Coloring
Cheeger's inequality and Fiedler's algorithm Expansion
Sparsest cut and Leighton-Rao algorithm Leighton Rao relaxation
Random walk and expanders Random walks
Solving Laplacian linear systems and sparsification Laplacian linear equations

References

Convex Programming

Linear Algebra

Spectral Graph Theory

Grading