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

- 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