6.S978 Graphs, Linear Algebra, and Continuous Optimization


Units: 3-0-9
Prerequisites: 18.06, 6.006, 6.046 recommended, 6.041 or 18.600
Instructor:  Prof. Aleksander Madry
Schedule: TR2:30-4, room 24-307
This subject offers a tour through the ideas and concepts that underlie the development of fast graph algorithms using tools of continuous optimization and linear algebra. Along the way, it will cover basics of continuous optimization (gradient descent, constrained optimization, interior-point methods), elements of spectral graph theory, as well as some more advanced graph algorithmic techniques (sparsification, graph partitioning).