I plan to cover the following topics:

• Basics (2 weeks): Eigenvalues and graph properties, examples, Laplacian, eigenvalue interlacing.
• Expanders and Extremal Graphs (3 weeks): Cayley graphs, strongly regular graphs, measures of expansion, expander mixing lemma, Cheeger's inequality, expander constructions.
• Random Walks (2 weeks): Random walks on undirected graphs, application to randomness-efficient error reduction, random walks on directed graphs and PageRank.
• Partitioning and Clustering (1-2 weeks): Graph coloring, higher order Cheeger inequalities, algorithms.
• Graph Sparsification (2 weeks): Effective resistance, cut sparsifiers, spectral sparsifiers, matrix Chernoff bound, algorithms.
• Solving Laplacian Systems (1 week): Iterative methods for linear systems, preconditioning.
• High Dimensional Expanders (2-3 weeks): Definitions, local to global, random walks, connection to sampling, constructions.

I will draw on a variety of material, including the following books and lecture notes:
Dan Spielman
Luca Trevisan
Salil Vadhan
David Williamson
van Lint and Wilson
Norman Biggs

• Algebra, including vector spaces, eigenvectors/eigenvalues, and finite fields;
• Discrete Probability, including moments and deviation bounds of Markov, Chebyshev, and Chernoff;
• Combinatorics, at least basic combinatorics and graph theory;
• Algorithms, including their analysis and the notion of polynomial time.

Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking 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, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.