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 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.

*Spectra of graphs*by Brouwer and Haemers.*Random walks and electric networks*by Doyle and Snell.- 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.

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

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 |

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