Course website (including Spring 2023 materials & Q evaluation): https://sites.google.com/g.harvard.edu/sgt
Course preview from 1/18/23: video recording and whiteboard
Lecture times: Monday & Wednesday, 9:45-11:00am, starting January 26
Lecture location: SEC LL2.221, 150 Western Ave, Allston.
Instructor: Salil Vadhan (he/they)
http://salil.seas.harvard.edu/, salil_vadhan@harvard.edu
Office hours posted at salil.seas.harvard.edu; usually also available for 15-30min after class.
Teaching Fellow: Prashanth Amireddy (he/him)
https://sites.google.com/view/prashanth-amireddy, pamireddy@g.harvard.edu
Course Assistant: Easton Singer (he/him)
esinger@college.harvard.edu
Whenever possible, please post questions for the course staff on Ed (privately if needed) rather than emailing us, so that we can all see the question and responses.
Spectral graph theory is about how eigenvalues, eigenvectors, and other linear-algebraic quantities give us useful information about a graph, for example about how well-connected it is, how well we can cluster or color the nodes, and how quickly random walks converge to a limiting distribution. Spectral graph theory has turned out to be extremely useful in theoretical computer science, with applications ranging from solving linear systems, converting randomized algorithms to deterministic algorithms, sampling via Markov Chain Monte Carlo, counting, web search, and maximum flow. In this course, we will study both the mathematics and the algorithmic applications of spectral graph theory, including some results from the past couple of years. Along the way, we will cover a number of concepts and tools that are quite broadly useful, such as mixing of Markov chains, expander graphs, algorithmic linear algebra, and the multiplicative weights method for optimization. Spectral graph theory has also played a role in a number of other fields, such as multi-robot systems, computer vision, epidemiology, network economics, and combinatorics, which you will have the possibility of exploring through your course projects.
By the end of the course, we hope that you will all be able to:
Comfortably use linear-algebraic tools in designing algorithms and in studying graph-theoretic problems,
Extract both the high-level ideas and low-level details when reading a text and identify interesting questions that are not answered,
Explain and collaboratively work through an advanced theory subject with your peers,
Understand the state of the art in algorithmic spectral graph theory as needed to engage in research in this area and/or apply it to other areas.
Formulate and carry out an interesting, short-term independent project, and present the work in both written and oral form.
Algorithms at least at the level of CS 1200; a strong understanding of linear algebra, at least at the level of AM 22a or Math 21a; probability at least at the level of Stat 110, and mathematical maturity and comfort with proofs at least at the level of CS 121 or 124 or 100-level Math courses. Problem Set 0 (which is required) will be a good way to gauge your preparation for the course and what review you may need to do. If this your first graduate-level CS theory course, be prepared for a significant jump in expectations compared to undergraduate theory classes, in terms of the pace, difficulty of homework problems, and level of independence expected (e.g. you may need to self-study some background material, even if it is not explicitly covered in the aforementioned prerequisites).
The main components of the course are as follows:
Main class meetings (MW 9:45-11): These will be interactive lectures, with the exposition and discussion guided by student questions and comments, interspersed with occasional problem-solving and brainstorming in small groups.
Section (every other week, time TBD): Section will be held every other week, at a time TBD to accommodate as many students as possible. The sections will include guided work on practice problems, review of difficult concepts, and supplementary material. Attendance is not required.
Office hours (every week, at multiple times TBD): Salil and any TFs will hold office hours at multiple times of the week.
Reading and commenting: To allow our class meetings to be more interactive, short advance reading will be assigned for most class meetings, and you will be expected to comment on those readings using the social e-reader Perusall. The pre-reading and your commenting will help us focus our class meetings on the material that is most confusing or most interesting, will give you experience in working through advanced material with your peers, and can lead to interesting discussions or project/research ideas.
Problem sets: There will be approximately 5 problem sets due approximately every other week, typically on Fridays at 5pm. Some of the problems may require deep thought, so you are strongly encouraged to begin them early and to brainstorm in groups of 2-3 students. (See Collaboration Policy below.)
Final project: You will do a group final project on a topic of your choosing. Projects should be done in groups of size 3-5, with the scope and ambition proportional to the group size. Projects can involve implementing and experimenting with some of the algorithmic techniques in this area, giving an original presentation of material from the research literature that we didn’t cover in class, and/or trying to obtain some new theoretical results. The project should provide good opportunities to connect the course material to your other interests and get some exposure to the frontier of research in spectral graph theory. The project will involve submitting topic ideas for feedback (initially with problem set 2 and then revised with a group by Wed 4/1), a detailed project proposal (due Friday 4/10), a written paper (draft due Fri 5/1, final version due Tue 5/12), and a project presentation (due Fri 5/8). We will post more details about the final project early in the course.
Asynchronous Q&A and discussion: We will use Ed for Q&A, announcements, and discussions that are not attached to specific readings.
The final grades for the course will be determined by roughly the following breakdown:
50% Problem Sets
25% Participation (in class meetings, section, office hours, Perusall, and/or Ed)
25% Final Project
You will have 5 late days for problem sets during semester, of which you can use up to 5 days on any one problem set. For the 4 group project deadlines, your group can use up to 4 late days in total (but note that submitting late on a checkpoint means that you may receive feedback later too). Do not use your late days carelessly at the start of the term; save them for unexpected circumstances when you might really need them. Any extensions beyond this late-day allocation requires a note from your resident dean (for undergraduates) or faculty advisor (for graduate students).
We would like to create a learning environment in our class that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, ability, etc.). We (like many people) are still in the process of learning about diverse perspectives and identities. If something was said in class (by anyone) that made you feel uncomfortable, please talk to us about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please don’t hesitate to come and talk with us. As a participant in course discussions, you should also strive to be open-minded and respectful of your classmates. (Based on text by Dr. Monica Linden at Brown University.)
If you have a physical or mental health condition that affects your learning or classroom experience, please let us know as soon as possible so that we can do our best to support your learning (at minimum, providing all of the accommodations listed in your DAO letter if you have one). (Statement adopted from one by Prof. Krzysztof Gajos at Harvard University.)
Everyone can benefit from support during challenging times. Not only are we happy to listen and make accommodations as needed, we can also refer you to additional support structures on campus, including, but not limited to, the below.
Counseling and Mental Health Services, 617-495-2042
Harvard College Peer Counseling, 617-495-4969
Students are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people). Discussion of homework problems may include brainstorming and talking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently of each other, and these write-ups should not be checked against each other or passed around.
Generative AI tools may be used to better understand the course material, or the concepts in a homework problem, but you should not use an AI tool for brainstorming or writing up your solution. In particular, you should not enter the homework problem itself as part of the prompt to an AI model. While working on your problem sets, you should not refer to existing solutions, whether from other students, past offerings of this course, materials available on the internet, or elsewhere.
All sources of ideas on assignments (whether homework or course project components), including the names of any collaborators (including AI tools and people outside of the course), must be listed on your submission along with a brief description of how they influenced your work. You do not need to cite the lecture notes or section notes. If you use any concepts, terminology, or problem-solving approaches not covered in the course material by that point in the semester, you must describe the source of that idea. If you credit an AI tool for a particular idea, then you should also provide a primary source that corroborates it. You should also explicitly acknowledge any use of AI for typesetting or formatting your solutions.
In general, we expect all students to abide by the Harvard College Honor Code. We view us all (teaching staff and students) as engaged in a shared mission of learning and discovery, not an adversarial process. The assignments we give and the rules we set for them (such as the collaboration policy) are designed with the aim of maximizing what you take away from the course. We trust that you will follow these rules, as doing so will maximize your own learning (and thus performance on exams) and will maintain a positive educational environment for everyone in the class. We welcome and will solicit feedback from you about what more we can do to support your learning.
You may find some of the following resources useful in addition to the class lecture notes.
Lap Chi Lau. Algorithmic Spectral Graph Theory.
Daniel A. Spielman. Spectral and Algebraic Graph Theory.
Luca Trevisan. Lecture Notes on Graph Partitioning, Expanders, and Spectral Methods.
Nisheeth Vishnoi. Lx=b.
The introduction to the Spielman text also includes pointers to background material, for example on linear algebra. Another useful reference are the tutorial videos from the Algorithmic Spectral Graph Theory Boot Camp at the Simons Institute for the Theory of Computing.
(Bracketed items are contingent on time available.)
Basics
Classes of graphs (from simple undirected graphs to weighted digraphs)
Associated matrices (adjacency, random-walk matrix, Laplacians)
Linear algebra (Spectral Theorem, Courant-Fischer, Perron-Frobenius)
Markov chains
Stationary distributions
Mixing time and 2nd eigenvalue
Power method
Pagerank
Markov Chain Monte Carlo (MCMC) for sampling and counting
Spectral partitioning and clustering
Spectral bounds on graph coloring
Cheeger’s Inequality and spectral partitioning
Higher-order Cheeger and spectral clustering
Partitioning of planar graphs
Expander graphs
Spectral vs. combinatorial definitions
Existence
Application to derandomization: Undirected S-T Connectivity in Logspace
[Expander decompositions and algorithmic applications]
Resistor networks and spanning trees
Effective resistances and Schur complements
Matrix-Tree Theorem
Random spanning trees
Spectral sparsification
Spectral approximation of matrices
Sparsification via random sampling
[Sparsification via rank-1 updates]
Solving Laplacian systems
Preconditioned Richardson iterations
A nearly linear-time randomized algorithm and a nearly logarithmic-space deterministic algorithm
Applications (the power method, possibly others)
[Other Applications of Spectral Graph Theory]
Graph drawing
Consensus protocols
Epidemiology
[High-dimensional expanders]
Basic theory
Application to sampling random spanning forests and matroid bases
[Solving directed Laplacians]
Spectral approximation of digraphs
Algorithm(s) for Eulerian Laplacians
Reduction from general digraphs to Eulerian digraphs
[Interlacing families]
Bipartite Ramanujan graphs of all sizes and degrees
Eliminated problem set 5, but made problem set 0 mandatory.
Increased amount of time available for project description and draft project paper, via the reduction in the number of problem sets.
Will try to make the required pre-reading for each class shorter and more focused.
May replace some topics that overlap with this term’s CS 2253, e.g. High-Dimensional Expanders.