Fall 2023, Brown University
Course Syllabus
See here; this mostly summarizes this webpage
Time and Location
Wednesday, 3:00pm – 5:30pm, CIT 241
Instructor
Ellis Hershkowitz, CIT 507
Office Hours
Wednesday, 2:00pm-3:00pm, CIT 507
Graphs are one of the most powerful and flexible algorithmic tools. Likewise, graph algorithms remains a primary focus of modern algorithms research. This course will sample major results from contemporary paradigms of graph algorithms. Particular attention will be paid to techniques in graph sparsification and how these techniques have helped to recently solve open problems in algorithms. Planned topics include: metric embeddings, expander decompositions, iterative rounding, edge-degree constrained subgraphs and palette sparsification.
This course is aimed at current and potential future graduate students considering proof-based research in algorithms. Each student will be responsible for reading and presenting a paper with the goal of better understanding how contemporary research in theoretical computer science is both done and best communicated.
Prerequisites:
The only official pre-requisites for the class is either CSCI1570 or CSCI1550 (CSCI1450 also works).
That said, you should be “mathematically mature” and have experience with formal proofs. Ideally, you have some background in and comfort with proof-based algorithm design and analysis. A strong background in probability will also be helpful for many of the papers.
If you’re unsure if you have an appropriate background feel free to reach out and we can discuss!
Each student (or pair of students) will be assigned one of the below papers. Student pairs will be assigned to the more complicated papers. The below summarizes everything you’ll have to do for this class:
Here’s a recommended rough breakdown of the timing of your talk:
You should be able to access the papers through the links below using your Brown credentials (let me know if you have trouble). I’ll give the first two lectures and the first student lecture will be on September 20th. You definitely don’t need all the relevant background to read a given paper but in deciding what papers to choose you may find it easier to read papers in which you have some background. Many of these papers have nicely-digested talks or scribe notes summarizing them that I’ve tried to provide where possible.
| Date | Topic | Paper | Presenter | Notes | Relevant Background | Useful Links | Slide Links |
|---|---|---|---|---|---|---|---|
| Sep 6 (Wed) | Overview of Class and Papers | Ellis | First day slides | ||||
| Distance Sparsification | |||||||
| Sep 13 (Wed) | How to Read, Present and Listen to Theory + Spanners | On Sparse Spanners of Weighted Graphs (Paper for Class) | Ellis | Graph Girth | This spanners survey by Ahmed et al. | Reading, Presenting and Listening to Theory Slides, Spanners Mini-Talk Slides | |
| Sep 20 (Wed) | Steiner Point Removal | Steiner Point Removal with Distortion O(log k) using the Relaxed-Voronoi Algorithm | Howie | Focus on first 4 sections | Randomized Algorithms, Probability, Concentration Bounds | A talk by Arnold on this | |
| Sep 27 (Wed) | CKR Cutting Scheme (and 0-Extension) | Approximation Algorithms for the 0-Extension Problem | Will | Randomized Algorithms, Probability, Concentration Bounds | Scribe notes of Anupam Gupta+Shobha Venkataraman | ||
| Oct 4 (Wed) | Tree Embeddings | A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics | Yeganeh | Makes use of CKR cutting scheme from previous week. Consider presenting an application from the relevant chapter in this book | Randomized Algorithms, Probability, Concentration Bounds | Scribe notes by Mike Dinitz | |
| Flow/Cut Sparsification | |||||||
| Oct 11 (Wed) | Sampling-Based Cut Sparsification | Approximating s–t Minimum Cuts in Tilde O of N Squared Time | Alan | Randomized Algorithms, Probability, Concentration Bounds, Graph Cuts, Parallel Algorithms | Scribe notes of Mohsen Ghaffari and Jakob von Kalle | ||
| Oct 18 (Wed) | Tree Flow Sparsifiers | Optimal Hierarchical Decompositions for Congestion Minimization in Networks | Fahad | Makes use of tree embeddings from two weeks ago. For applications feel free to only do oblivious routing. Ellis away at workshop; Yu Cheng to sub | Randomized Algorithms, Probability, Concentration Bounds, Graph Flows, Distributed Algorithms | Chapter 15.2 of this book | |
| Oct 25 (Wed) | Expander Decompositions and Pruning | Expander Decomposition and Pruning: Faster, Stronger, and Simpler | Binhao+Ryan | Feel free to ignore appendices | Expanders, Graph Flows, Dynamic Algorithms | Tutorial 1 and Tutorial 2 of Thatchaphol Saranurak on expander decompositions. See also relevant talks from this class | |
| Nov 1 (Wed) | Steiner Point Removal Lower Bound |
A Tilde Omega Root Log |T| Lower Bound for Steiner Point Removal |
Apoorv | Quite short. Gives the first non-constant lower bound for SPR as defined in previous week. |
Randomized Algorithms, Probability, Concentration Bounds |
Similar to the Theorem 4.1 construction in this paper; may or may not be helpful to look at. |
|
| Matching Sparsification | |||||||
| Nov 8 (Wed) | Edge-Degree-Constrained Subgraphs | Faster Fully Dynamic Matchings with Small Approximation Ratios | Francisco | Ellis away at conference, Yu Cheng to sub | Matching Theory, Approximation Algorithms, Dynamic Algorithms | This talk by Aaron Bernstein | |
| Coloring Sparsification | |||||||
| Nov 15 (Wed) | Palette Sparsification | Sublinear Algorithms for (Δ + 1) Vertex Coloring | Klimentina | Randomized Algorithms, Probability, Concentration Bounds, Streaming Algorithms, Sublinear algorithms, Parallel Algorithms | This talk by Sanjeev Khanna | ||
| Nov 22 (Wed) | No class, Thanksgiving Break | ||||||
| Fractional Optima Sparsity | |||||||
| Nov 29 (Wed) | Survivable Network Design | A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem | Bin | Linear Algebra, Linear Programs, Approximation Algorithms, Network Design Algorithms, Uncrossing | This book on iterative rounding. See 4.1 for the simplest application of iterative rounding (that I know of) to a problem (here minimum spanning tree). | ||
| Dec 6 (Wed) | Bounded Degree Spanning Trees | Minimum Bounded Degree Spanning Trees | Richard | Linear Algebra, Linear Programs, Network Design Algorithms, Approximation Algorithms, Uncrossing, Graph Arboricity | Same as previous week |
Some Good Talks
Here are some example talks by people I feel generally give good talks. I’ve tried to choose topics across a variety of areas of algorithms. I haven’t watched all of the below.
Some Links About Doing/Writing/Reading/Presenting Theory/Math:
Here are some more general links to both talks and blog-post-type writings of various theoreticians and mathematicians that you might find useful.
If you feel you have a disability that could affect your performance in the course, please contact SAS and ask them to contact me. I’ll do whatever I can to support recommended accommodations.
Doing theory is extremely difficult if you aren’t feeling physically and mentally well, included and supported by your peers and mentors or otherwise marginalized.
My hope is that this is a welcoming and inclusive course. If you feel you have been mistreated please feel free to contact me directly or consider reaching out to some of the student advocates in the department. If you feel you might be the victim of harassment, consider reaching out to the Brown Title IX Office.
If you feel you are overstretched or otherwise psychologically distressed I encourage you to reach out to Brown CAPS. You may also find these resources from Brown Health and Wellness (and links therein) useful.