18.434 Seminar in Theoretical Computer Science

Spring 2020

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 algebraic and spectral graph theory with applications. Potential subtopics include random walks, graph partitioning, sparsification, coloring, random graphs, expanders, and myriad algorithmic and complexity-theoretic applications.

Course Information

Instructor: Cole Franks.

Susan Ruff is helping us with the communication aspects of the course.

When and where: TTh 1-2: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). Stellar http://stellar.mit.edu/S/course/18/sp20/18.434/ will be used primarily for collecting assignments.

Office hours: Mostly by appointment, but there will be drop-in hours Wed 4-5 in 2-241. Susan has office hours Thu 4:30-5:30 pm in 2-370 and by appointment.

Prerequisites: A course in algorithms at the level of 6.046.

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 talk on the same subject as the final paper. Additionally, there will be a handful of problem sets to be typset in LateX (25%), and in-class participation (15%). Attendance is mandatory and more than 3 unexcused absences will result in failure. You must visit S3 to have your absences excused.

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

Dates: These are subject to change.

  1. 2/21/2020 Pset 1 due
  2. 3/4/2020 Pset 2 due
  3. 3/18/2020 Pset 3 due
  4. 3/20/2020 Final paper topic due
  5. 4/6/2020 First draft of final paper due
  6. 4/10/2020 Pset 4 due
  7. 4/17/2020 First draft of final paper due
  8. 4/25/2020 Pset 5 due
  9. 5/8/2020 Pset 6 due
  10. 5/17/2020 Final paper due

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.

Date Presenter Topic Source
Tu Feb 4, 2020 Cole + Susan Adjacency matrix/Laplacian + Communication BH 1.1, 1.2, 1.3
Th Feb 6, 2020 Cole + Susan Spectral theorem, examples + communication BH 1.4
Tu Feb 11, 2020 Collin + Turbat Matrix Tree Theorem + Graph decompositions BH 1.3.5 + BH 1.3.6, 1.5
Th Feb 13, 2020 Qi + Baris Perron Frobenius Theory + Rayleigh Quotient, Interlacing BH 2.2,3.1 + BH 2.4,1.7,2.5,3.2
Tu Feb 18, 2020 President's day
Th Feb 20, 2020 Deon + Max Regular/bipartite graphs + Chromatic number BH 2,1,3.3,3.4 + BH 3.5-3.6
Tu Feb 25, 2020 Thomas + Agustin Shannon capacity + Cayley Graphs BH 3.7 + BH 6.1-6.3, Spielman 5
Th Feb 27, 2020 Daniel Ranking,Cutting,Drawing, Clustering BH 3.13.2,3, BH 3.13.4,5, spielman 1
Tu Mar 03, 2020 Robert + Julian Alon-Bopanna + Expander Mixing Lemma BH 4.1 + BH 4.3, Spielman 15
Th Mar 05, 2020 Ramya + Josh Cheeger's intro, easy direction + Cheeger hard direction BH 4.4, Speilman 6
Tu Mar 10, 2020 Alex + Yejin Clustering + Moore Graphs BH 3.13.4,5, spielman 1 + Fox 19
Th Mar 12, 2020 Susan Ruff Presentation Workshop
Tu Mar 17, 2020 TBD + TBD TBD TBD
Th Mar 19, 2020 TBD + TBD Electrical networks, Springs + Random Walk DS 1.1-1.3, Spielman 7
Tu Mar 24, 2020 Spring break
Th Mar 26, 2020 Spring break
Tu Mar 31, 2020 TBD + Susan Random walk mixing + Writing workshop Lovasz, Probability on Graphs
Th Apr 2, 2020 TBD + TBD Polya's theorem 2d + Polya 3d DS 2.1,2.2 + DS 2.2
Tu Apr 7, 2020 TBD + TBD Pseudorandomness: error reduction Spielman 11
Th Apr 9, 2020 TBD + TBD Effective Resistance + Schur Complement Spielman 8
Tu Apr 14, 2020 TBD + TBD Iterative solvers for linear equations Spielman 12
Th Apr 16, 2020 TBD + TBD Graph Drawing + Tutte's planar embedding theorem Spielman 1,2 + Spielman 9
Tu Apr 21, 2020 TBD + Susan/Cole Planar Graph Spectral gap + slides workshop Spielman 20
Th Apr 23, 2020 TBD + everyone Block stochastic model (partitioning) + peer paper review Spielman 21
Tu Apr 28, 2020 3-4 final presentations
Th Apr 30, 2020 3-4 final presentations
Tu May 5, 2020 3-4 final presentations
Th May 7, 2020 3-4 final presentations
Tu May 12, 2020 3-4 final presentations

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.
  1. Ranking algorithms, e.g. pagerank
  2. Image segmentation/clustering, e.g. Nyström method
  3. SL = L (Reingold, exposition by Trevisan)
  4. Sensitivity Conjecture (Huang)
  5. Sparsest cut (ARV, exposition by Trevisan)
  6. Graph sparsification via effective resistances (Spielman, Srivastava)
  7. Linear size sparsifiers BSS
  8. Preconditioning/sparsification for iterative solvers (Spielman 12,13,14)
  9. Constructions of expanders, e.g. Zig-zag product of Reingold, Vhadan, Wigderson (Spielman 16, RVW)
  10. Random spanning trees (Aldous, Broder)
  11. Expected characteristic polynomials (MSS)
  12. Sorting networks (Ajtai, Komlos, Szemeredi)
  13. Lovasz, Vectors Graphs and Codes (Alon)
  14. Equiangular lines ( Jiang, Tidor, Yao, Zhang, Zhao )
  15. PCP Theorem (Dinur, exposition by Radhakrishnan, Sudan)
  16. Tao, Kannan, Frieze's Spectral proof of Szemeredi Regularity Lemma
  17. Matroid basis sampling algorithms Feder, Mihail