*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:

- Fill out form of top 3 papers after shopping period
- Read your assigned paper
- Prepare and give your talk on the paper with at least 6 pre-prepared questions for the audience in your talk
- Schedule a time the week before your talk to practice the introduction portion with me (and do so)
- Actively participate in class and give feedback at the end of each talk

Here’s a recommended rough breakdown of the timing of your talk:

*Introduction:*~30 minutes*Break:*~20 minutes*Technical Details:*~60 minutes*Feedback from the Class:*~15 minutes

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) | The Expander Hierarchy and its Applications to Dynamic Graph Algorithms | Michael+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 | Expanders, Graph Flows, Dynamic Algorithms | Same as previous week | |

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 |

- 90% presentation, feedback form with talk goals here.
- 10% in-class participation

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

- Roie Levin (Brown Alum!) on Random Order Set Cover is as Easy as Offline (online, approximation algorithms)
- Ellen Vitercik on How Much Data is Sufficient to Learn High-Performing Algorithms? (machine-learned algorithms)
- Thatchaphol Saranurak on Recent Applications of Expanders to Graph Algorithms (fast sequential, dynamic, distributed algorithms)
- Merav Parter on Graph Shortcuts: New Bounds and Algorithms (parallel, distributed, dynamic algorithms)
- Jelani Nelson on Recent Advances in Streaming and Private Heavy Hitters (sketching, streaming algorithms)
- Anupam Gupta on Robust Algorithms for Secretaries and Bandits (online, approximation algorithms)
- Rico Zenklusen on Approximation Algorithms for Hard Augmentation Problems (approximation, network design algorithms)

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

- Anupam Gupta on presenting theory
- Talk by Ryan O’Donnell on doing/reading/presenting theory
- Nicole Wein on doing theory as an early-stage PhD
- Ravi Vakil’s three things exercise for attending talks
- Ravi Vakil’s general advice (for math PhD students)
- Overview of various relevant blog posts by Terry Tao on career advice
- Overview of various relevant blog posts by Terry Tao on writing papers

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.