## Linear algebraic tools in TCS (CS698B)

### 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

### 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.

### Convex Programming

• Convex Optimization, Boyd and Vandenberghe.
• Combinatorial Optimization: Algorithms and Complexity, Papadimitriou and Steiglitz.

### Linear Algebra

• Linear Algebra and its Applications, G. Strang.
• Matrix Analysis, Bhatia.