CSCI 1952C: Frontiers of Graph Algorithms Seminar

Fall 2023, Brown University

Course Syllabus
See here; this mostly summarizes this webpage

Time and Location
Wednesday, 3:00pm – 5:30pm, CIT 241

Ellis Hershkowitz, CIT 507

Office Hours
Wednesday, 2:00pm-3:00pm, CIT 507

Course Description

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.


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) Dynamic Tree Flow Sparsifiers (The Expander Hierarchy)

Steiner Point Removal Lower Bound
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

A Tilde Omega Root Log |T| Lower Bound for Steiner Point Removal
Apoorv Makes use of expander decompositions / pruning ideas from previous week. Quite lengthy. Focus just on first 5 sections, sketch 7 and 8 and only present 1 application from section 9

Quite short. Gives the first non-constant lower bound for SPR as defined in previous week.
Expanders, Graph Flows, Dynamic Algorithms

Randomized Algorithms, Probability, Concentration Bounds
Same as previous week

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  


Other Resources

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.

Student Well-Being

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.