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, ruff@math.mit.edu, 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/6/2020 Pset 2 due
  3. 4/1/2020 Extension! Pset 3 due
  4. 3/30/2020 Final paper topic due
  5. 4/14/2020 First draft of final paper due; First draft is now a summary; see the final draft section for details.
  6. 4/17/2020 Pset 4 due
  7. 4/29/2020 Extension! Second draft of final paper due
  8. 5/8/2020 Extension! Pset 5 due
  9. 5/12/2020 Final paper due

Psets

  1. Pset 1 , tex file
  2. Pset 2 , tex file
  3. Pset 3 , tex file
  4. Pset 4 , tex file
  5. Pset 5 , tex file

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:
  1. Eigenvalues of random symmetric matrices
  2. Linear size sparsifiers, Spielman 18
  3. Sparsification by effective resistance random sampling, Spielman 17
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 Properties of graphs from their spectra + 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 Lazy random walks + Cheeger hard direction Spielman 10, Speilman 6
Tu Mar 10, 2020 Yejin + Alex Moore Graphs + Clustering Fox 19 , BH 9.1 + Trevisan 7
Th Mar 12, 2020 Susan Ruff Presentation Workshop + choosing final topic
Tu Mar 17, 2020 No Class
Th Mar 19, 2020 No Class
Tu Mar 24, 2020 Spring break
Th Mar 26, 2020 Spring break
Tu Mar 31, 2020 Susan + Cole Writing workshop + Review TBD + example exposition.
Th Apr 2, 2020 Qi + Max Pseudorandom generators from expanders + Construction of expanders Spielman 11 + Spielman 16
Tu Apr 7, 2020 Julian + Thomas Sensitivity Conjecture + Probabilistic interpretations of voltage and current Huang+ DS 1.3.1-1.3.3, Spielman 7
Th Apr 9, 2020 Collin + Agustin Effective resistance and Schur complements + Polya's theorem 2d DS 1.3.4, Spielman 8 + DS 1.3.5, 1.4.1, 2.2.1
Tu Apr 14, 2020 Turbat + Cole Polya 3d + Review DS 2.2.4 - end of 2.2
Th Apr 16, 2020 Robert + Daniel Tutte's theorem on planar graph drawing + Second eigenvalue of planar graphs Spielman 9 + Spielman 20
Tu Apr 20, 2020 7:00 pm EDT Yejin Iterative solvers for linear equations Spielman 12
Tu Apr 21, 2020 Deon + Baris Conjugate gradient and graph diameter + Maxcut Spielman 13 + Naor
Th Apr 23, 2020 Josh + Ramya Preconditioning, low stretch spanning trees + Fast Laplacian solvers by sparsification Spielman 14 + Spielman 19
Tu Apr 28, 2020 Alex + Qi Quasirandom graphs Alon and Spencer 3rd edition Section 9.3
Th Apr 30, 2020 Tom + Deon + Daniel
Tu May 5, 2020 Collin + Max + peer review
Th May 7, 2020 Agustin + Alex + Turbat
Tu May 12, 2020 Robert + Josh + Julian

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. Because we missed a week and things have gone remote, 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

Because time has been shortened, I am reducing the load for the first draft and extending the deadline 1 day (Tues Apr 14). 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).

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. Robert: Ranking algorithms, e.g. local pagerank
  2. Daniel: Pagerank Second eigenvalue of Google matrix
  3. Turbat: Image segmentation/clustering, e.g. Nyström method
  4. Alex: SL = L (Reingold, exposition by Trevisan, or via Derandomized squaring Rozenman, Vadhan)
  5. Deon: Sparsest cut (ARV, exposition by Trevisan)
  6. TBD: Constructions of expanders, e.g. Zig-zag product of Reingold, Vhadan, Wigderson (Spielman 16, RVW)
  7. Collin: Random spanning trees (Aldous, Broder)
  8. TBD: Expected characteristic polynomials (MSS)
  9. Max: Sorting networks (Ajtai, Komlos, Szemeredi)
  10. Agustin: Lovasz, Vectors Graphs and Codes (Alon)
  11. Qi: Equiangular lines ( Jiang, Tidor, Yao, Zhang, Zhao )
  12. Tom: PCP Theorem (Dinur, exposition by Radhakrishnan, Sudan)
  13. Yejin: Tao, Kannan, Frieze's Spectral proof of Szemeredi Regularity Lemma
  14. Julian: Matroid basis sampling algorithms Feder, Mihail
  15. Josh + Ramya : Community detection Alon, Krivelevich, Sudakov
  16. TBD: Block stochastic models: source TBD, paper would include both algorithmic results and impossibility results.