18.434 Seminar in Theoretical Computer Science

Spring 2022

This is an undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. As with all CIM subjects, the emphasis is on communication, both oral and written. Enrollment is limited by the department. The topic this spring is spectral graph theory with applications. Potential subtopics include random walks, graph partitioning, sparsification, coloring, random graphs, expanders, and myriad algorithmic and complexity-theoretic applications. Topics are flexible and applications of spectral methods and numerical linear algebra beyond graph theory are welcome.

Course Information

Instructor: Cole Franks.

Susan Ruff, ruff@math.mit.edu, is helping us with the communication aspects of the course.

When and where: TTh 11-12:30 pm in 2-151

Books: I will send you links for materials as we need them, but we will start with the following.

  1. Spectra of graphs by Brouwer and Haemers.
  2. Random walks and electric networks by Doyle and Snell.
  3. Lecture notes from a course on Spectral Graph Theory taught at Yale by Dan Speilman.

Websites: Most information will be on http://math.mit.edu/~franks/18.434.html (this site). Canvas (https://canvas.mit.edu/courses/12946) will be used primarily for collecting assignments.

Office hours: Mostly by appointment, but there will be drop-in hours Tues 3-4 in 2-181.

Prerequisites: A course in algorithms at the level of 6.046. Linear algebra will be helpful.

Assessment: Everyone will be expected to give three talks (40%) and write a final paper (20%). The first two talks will be chalk talks, and the final talk will be a slide presentation for the final paper. Additionally, there will be a handful of problem sets to be typset in LateX (25%), and in-class participation (15%). In class partipation includes moderator duties. Attendance is mandatory and more than 3 unexcused absences will result in failure. You must visit S3 to have your absences excused, but this is not a guarantee. The more advanced notice you can give me about the absence, the more lenient I wil be. If you are required to isolate during a scheduled presentation, you can either present via Zoom (unless, of course, you are too ill to present) or help me try to find someone to switch with you.

Here is a rubric for how I will grade chalk talks.

Dates:

  1. 3/30/2020 Final paper topic due
  2. 4/15/2020 First draft of final paper due
  3. 5/02/2020 Second draft of final paper due
  4. 5/10/2020 Final paper due

Psets

At most bi-weekly, around 3 questions. Pset questions may refer to material presented by classmates. Pset 1 to be posted at end of first week, due Feb 18.
  1. Pset 1 , tex file
  2. Pset 2 , tex file
  3. Pset 3 , tex file
  4. Pset 4 , tex file

Guidelines for giving talks

The first two talks (the chalk talks) will be 35-40 minute talks about some topic or result from spectral graph theory or a related field. From the schedule below you'll see that presentation slots come with a suggested topic. I have tried to choose these so that there will be a clear result to take as the main focus. The goal of the talks is to teach the result and its proof to your colleagues. Your talk can be somewhat like a math lecture in a course, but should be self contained and well-motivated. The talk should contain, at the very least,

  1. An introduction explaining definitions and motivation for the result you will present. You should also mention your sources here.
  2. A statement and proof of the result or results which is understandable and engaging to your peers.
Sources such as Brouwer and Haemers can often be very terse - simply rewriting what you find there won't suffice, because there are many omitted details. You may need to fill in these details yourself or use other sources to do so - if you do use other sources, make sure to mention them. You are welcome to use other sources also to find motivation or better proofs for the results, and you are also welcome to ask me about anything you are struggling with. I'll also ask you to share your talk notes with me so I can share with the rest of the class in case they need them for the psets.

Tentative Schedule

We will start with Chapters 1-6 of Haemers. From there we will move to Doyle and Snell, and then we will fill in the rest with Spielman and other sources.

If for some reason you can't stand your topic you can come to me with another idea or choose from this (hopefully growing) list of extra topics. They tend to be more advanced than the topics in the schedule. What ties these additional topics together is the appearance of spectra of matrices in computer science and machine learning. The topics no one selects here can in some cases make good final presentation topics! If you have seen something elsewhere you think may qualify, please bring it to my attention.
  1. Eigenvalues of random symmetric matrices
  2. Linear size sparsifiers, Spielman 18
  3. Matrix completion, Benjamin Recht
  4. Hubs and authorities; Kleinberg's HITs algorithm
  5. Principal components analysis; Chapter 1 of Ravi Kannan's "Spectral algorithms"
  6. Higher order Cheeger inequalities and clustering: Lau
  7. Johnson-Lindenstrauss Lemma for dimensionality reduction, e.g. Mahoney
For the second round of talks, I'll be marking talks that require more background learning as advanced.
Date Presenter Topic Source
Tu Feb 1, 2022 Cole Adjacency matrix/Laplacian + Communication BH 1.1, 1.2, 1.3
Th Feb 3, 2022 Cole + Susan Spectral theorem, examples + communication BH 1.4
Tu Feb 8, 2022 Shelli + Rui Matrix Tree Theorem + Graph decompositions BH 1.3.5 + BH 1.3.6, 1.5
Th Feb 10, 2022 Shashvat + Pawan Perron Frobenius Theory + Rayleigh Quotient, Interlacing BH 2.2,3.1 + BH 2.4,1.7,2.5,3.2
Tu Feb 15, 2022 Sherry + Shaden Properties of graphs from their spectra + Chromatic number BH 2,1,3.3,3.4 + BH 3.5-3.6
Th Feb 17, 2022 Jerry + Lay Shannon capacity + Cayley Graphs BH 3.7 + BH 6.1-6.3, Spielman 5
Tu Feb 22, 2022 No Class
Th Feb 24, 2022 Aruzhan + Diego Ranking + Drawing, cutting BH 3.13.2,3, BH 3.13.4,5, spielman 1
Tu Mar 01, 2022 Sebastian + Justin Alon-Bopanna + Expander Mixing Lemma BH 4.1 + BH 4.3, Spielman 15
Th Mar 03, 2022 Daniel + Victor Lazy random walks + Cheeger interesting direction Spielman 10, Speilman 6
Tu Mar 08, 2022 Alina + Max Moore Graphs + Clustering Fox 19 , BH 9.1 + Trevisan 7 + Lau
Th Mar 10, 2022 Cole Presentation Workshop + choosing final topic
Tu Mar 15, 2022 Aruzhan + Justin Tutte's theorem on planar graph drawing + Second eigenvalue of planar graphs Spielman 9 + Spielman 20
Th Mar 17, 2022 Shashvat + Daniel Pseudorandom generators from expanders + Construction of expanders Spielman 11 + Spielman 16
Tu Mar 22, 2022 Spring break
Th Mar 24, 2022 Spring break
Tu Mar 29, 2022 Rui + Sebastian Quasirandom graphs + Sensitivity Conjecture Alon and Spencer, 3rd edition section 9.3 + Huang
Tu Mar 31, 2022 Cole + Susan Writing workshop + Review TBD + example exposition.
Th Apr 5, 2022 Max + Lay Probabilistic interpretations of voltage and current + Effective resistance and Schur complements DS 1.3.1-1.3.3, Spielman 7 + DS 1.3.4, Spielman 8
Tu Apr 7, 2022 Alina + Sherry Polya's theorem 2d + Polya 3d DS 1.3.5, 1.4.1, 2.2.1 + DS 2.2.4 - end of 2.2
Tu Apr 12, 2022 Shaden + Victor Sparsification by effective resistance random sampling + Maxcut Spielman 17 + Naor
Th Apr 14, 2022 Jerry + Diego Iterative solvers for linear equations + Conjugate gradient and graph diameter Spielman 12 + Spielman 13
Tu Apr 19, 2022 Pawan + Shelli Preconditioning, low stretch spanning trees + Block stochastic models Spielman 14 + Spielman 19
Th Apr 21, 2022 Final presentations
Tu Apr 26, 2022 Final presentations
Th Apr 28, 2022 Final presentations
Tu May 3, 2022 Final presentations
Th May 5, 2022 Final presentations
Tu May 10, 2022 Final presentations

Final project

The final project will be a 4-6 page writeup covering a result related to spectral graph theory, plus a short (20 minute) slide presentation at the end of the semester. The topics listed below are only suggestions; you may have to look around a bit to find a suitable final topic. The goal of your writeup is not to regurgitate proofs but rather to explain the key ideas of the work without getting bogged down in the details. You may, if you wish, choose to work in groups of 2. If you choose this option, your length is instead 8-10 pages and your final presentation length is 30 minutes rather than 20 minutes.

Expectations for first draft

The first draft should be at minimum a 1-2 page summary (2-3 if group) consisting of the following:

  1. the main result in the paper you are writing about.
  2. the significance of this result.
  3. A sketch of the proof - this could consist of the main lemmas involved in the proof together with some guiding text about why they are true and how they fit together to prove the main result. This sketch should reflect, at a minimum, that you have read and understood the material.
  4. A paragraph at the end stating what details you will fill in to make the full 4-6 page doc (or 8-10 if you are a group).

Second draft rubric

Here's the second draft rubric, which also explains how the final will be graded. 2nd draft rubric

Possible final topics:

Here is a list of suggestions. Some are very broad/ambitious; discuss with me so we can narrow down the source material. You can also provide your own topic or use topics we didn't cover, subject to my approval. It is also possible for people to present different results in the same topic but you must discuss with me to make sure there is not too much overlap. There is also a page of topic suggestions for a course by Trevisan.
  1. Diego: Laplacian Eigenmaps
  2. Shaden: Survey of ranking algorithms, e.g. local pagerank
  3. Shelli and Sebastian: Kleinberg's HITs algorithm
  4. Second eigenvalue of Google matrix
  5. Jerry: Image segmentation/clustering, e.g. Nyström method
  6. SL = L (Reingold, exposition by Trevisan, or via Derandomized squaring Rozenman, Vadhan)
  7. Daniel: Sparsest cut (ARV, exposition by Trevisan)
  8. Shashvat: Constructions of expanders, e.g. Zig-zag product of Reingold, Vhadan, Wigderson (Spielman 16, RVW)
  9. Sherry: Random spanning trees (Aldous, Broder)
  10. Expected characteristic polynomials (MSS)
  11. Rui: Sorting networks (Ajtai, Komlos, Szemeredi)
  12. Alina: Lovasz, Vectors Graphs and Codes (Alon)
  13. Justin: Equiangular lines ( Jiang, Tidor, Yao, Zhang, Zhao )
  14. Lay + Pawan: PCP Theorem (Dinur, exposition by Radhakrishnan, Sudan)
  15. Tao, Kannan, Frieze's Spectral proof of Szemeredi Regularity Lemma
  16. Matroid basis sampling algorithms Feder, Mihail
  17. Victor: Community detection Alon, Krivelevich, Sudakov
  18. Block stochastic models: source TBD, paper would include both algorithmic results and impossibility results.
  19. Sobolev inequalities and heat kernels on graphs Chung,Yao
  20. Applications of Poincare inequalities on graphs, e.g. Gromov's theorem
  21. Spectra of random regular graphs using non-back tracking random walks Friedman, Puder
  22. Sampling from convex bodies and KLS conjecture KLS
  23. Compressed sensing and restricted isometry property Candes, Tao
  24. Linear sketching for numerical linear algebra Woodruff
  25. Aruzhan: Fast triangle counting in real graphs