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

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

### Spectral Graph Theory

- Spectral Graph Theory, Fan R. K. Chung.
- Course notes, Dan Spielman.
- Course notes, Luca Trevisan.

Grading

- 2 Quizzes: 10 + 10
- Midsem: 20
- Project: 30 (5+10+15)
- Endsem: 30