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. There will be broadly three parts of the course.
The first few weeks will be devoted to the basics of linear algebra. It will mostly be focussed on rank, eigenvalues and eigenvectors of matrices. This will prepare students for the two tools they will be studying later. 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. Finally, we will show some applications of linear as well as semidefinite programming in complexity theory. This part will introduce them to the concepts of relaxation and rounding. The second tool we will talk about is 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 also discuss spectral sparsification, which helps in designing solvers for linear equations.