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:00pm3: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, edgedegree constrained subgraphs and palette sparsification.
This course is aimed at current and potential future graduate students considering proofbased 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 prerequisites 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 proofbased 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 nicelydigested 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 MiniTalk Slides  
Sep 20 (Wed)  Steiner Point Removal  Steiner Point Removal with Distortion O(log k) using the RelaxedVoronoi 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 0Extension)  Approximation Algorithms for the 0Extension 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)  SamplingBased 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 nonconstant 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)  EdgeDegreeConstrained 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 blogposttype 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.