Jan-May 2024, CSE, IITH Logistics Instructor: Dr. Rakesh Venkat, CSE Department Course name: CS5030, Topics in Theoretical Computer Science Lecture timings: R-slot (Tue 2:30pm-4pm and Fri 4pm-5:30pm) Location: C-LH5 A-117, from 12th Jan onwards First meeting: Tue Jan 02nd, 2:30pm. Course Overview In this (iteration of the) course on Topics in Theoretical Computer Science, we will be looking at Spectral Graph Theory and Algorithms. Spectral Graph Theory deals with the use of eigenvalues and eigenvectors of matrices associated with a graph to understand its structural and combinatorial properties. Spectral algorithms broadly refers to a class of algorithms based on linear algebraic tools that exploit the properties of eigenvalues and eigenvectors of matrices associated with input data (often graphs). Spectral algorithms on graphs have come to occupy a central role in computer science, with diverse applications spanning both theory and practice. A few salient examples include estimating the conductance in networks, ranking nodes in web graphs, converting randomized algorithms to deterministic ones, designing error correcting codes, and finding sparse approximations to graphs (among many more). The course will look at the basics of spectral graph theory with a view towards exploring its various applications in Computer Science.