CS 698B: Linear algebraic tools in TCS

Time: 5:10-6:30 Tue-Thu, KD 102.

Anti-cheating policy from CSE Dept

Drop policy from CSE Dept

First course handout

Notes

Course 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

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.

References

Convex Programming

Linear Algebra

Spectral Graph Theory

Grading