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.
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.
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.
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: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 + TBD | Polya 3d + Sparsification by effective resistance random sampling | DS 2.2.4 - end of 2.2 + Spielman 17 |
Th Apr 16, 2020 | Robert + Daniel | Tutte's theorem on planar graph drawing + Second eigenvalue of planar graphs | Spielman 9 + Spielman 20 |
Tu Apr 21, 2020 | Yejin + Deon | Iterative solvers for linear equations + Conjugate gradient and graph diameter | Spielman 12 + Spielman 13 |
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 + Peer review | Quasirandom graphs | Alon and Spencer 3rd edition Section 9.3 |
Th Apr 30, 2020 | final presentations | ||
Tu May 5, 2020 | final presentations | ||
Th May 7, 2020 | final presentations | ||
Tu May 12, 2020 | final presentations |
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: