Workshop Details

In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this development, then give a tutorial on how to construct some of these tools, such as expander decomposition.

Thatchaphol Saranurak delivers Part 1 of the tutorial presentation "Expander Decompositions and Applications" at the DIMACS Workshop on Modern Techniques in Graph Algorithms held at Rutgers University on June 12, 2023 - June 15, 2023.

Abstract: In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this development, then give a tutorial on how to construct some of these tools, such as expander decomposition.

The DIMACS Workshop on Modern Techniques in Graph Algorithms presented major advances in the design of efficient graph algorithms that have occurred over the last decade. The goal of this workshop was to bring together researchers from different areas of graph algorithms to share the techniques that have been recently influential in their areas. Topics covered not only fast graph algorithms in the classical setting, but also algorithms in various computational models such as dynamic algorithms, streaming algorithms, and sublinear algorithms.

Video: [part 1]    [part 2]

In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this development, then give a tutorial on how to construct some of these tools, such as expander decomposition. 

Video: [part 1]   [part 2]

For an n-vertex digraph G = (V, E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to Õ(√n). Despite extensive research over the years, the question of whether one can reduce the diameter to o(√n) with Õ(n) shortcut edges has been left open. 

In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the √n diameter barrier. Specifically, we show an O(nω)-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n1/3). I also present time efficient algorithms for computing these shortcuts and explain the limitations of the current approaches. Finally, I will draw some connections between shortcuts and several forms of graph sparsification (e.g., reachability preservers, spanners).

Based on a joint work with Shimon Kogan (SODA 2022, ICALP 2022, FOCS 2022, SODA 2023).

[Video]

In this tutorial, I will discuss a new tool in graph cut algorithms called the isolating cuts lemma. Originally developed for the (global) minimum cut problem, the isolating cuts lemma has been a key ingredient in recent progress on longstanding questions in problems such as all-pairs minimum cuts, vertex connectivity, and connectivity augmentation. I will give a simple and self-contained proof of the lemma, discuss some extensions, and describe applications to some of the problems mentioned above. The tutorial will be self-contained. 

[Video]

In these talks I will first give an overview of our FOCS'22 paper [*] on solving minimum-cost flow in almost linear time. I will also mention a few follow-up works. Then we'll dig a bit deeper into two components of the algorithm:

(1) The L1 interior point method that yields our 'outer loop'. We'll see how it works, and touch on how it might be generalized. This method turns the problem of solving an LP into a sequence of simpler L1-regression-like problems, that we only need to solve very crudely to solve our LP. In the case of flow problems, these L1-regression problems turn into a particularly nice task, known as min-ratio cycle.

(2) The Dynamic Spanner construction that we use for edge sparsification inside our data structures. This construction allows us to maintain a sparse subgraph H of a dynamically changing input graph G, with a promise that all distances in G are well-approximated in H.

[*] "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time" by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva.

Video: [part 1]   [part 2]

In these talks I will first give an overview of our FOCS'22 paper [*] on solving minimum-cost flow in almost linear time. I will also mention a few follow-up works. Then we'll dig a bit deeper into two components of the algorithm:

(1) The L1 interior point method that yields our 'outer loop'. We'll see how it works, and touch on how it might be generalized. This method turns the problem of solving an LP into a sequence of simpler L1-regression-like problems, that we only need to solve very crudely to solve our LP. In the case of flow problems, these L1-regression problems turn into a particularly nice task, known as min-ratio cycle.

(2) The Dynamic Spanner construction that we use for edge sparsification inside our data structures. This construction allows us to maintain a sparse subgraph H of a dynamically changing input graph G, with a promise that all distances in G are well-approximated in H.

[*] "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time" by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva.

Video: [part 1]   [part 2]

One of the most common techniques in graph algorithms is graph sparsification. Given a graph G, a sparsifier H of G is a sparse subgraph that preserves some relevant properties of G. For example, every graph G contains a sparse subgraph H that preserves all cuts up to a (1+ε) factor (known as a cut sparsifier). Similarly, every graph G contains a sparse subgraph H that approximately preserves all shortest distances in G (known as a spanner).

In this tutorial, we focus on another classic graph problem: maximum matching. Does every graph G have a sparse subgraph H that approximately preserves information about matchings in G? It turns out that strong guarantees analogous to cut sparsifiers are not possible. We show that there is nonetheless a matching sparsifier with several nice properties, called an edge-degree-constrained subgraph (EDCS). We prove several properties about the EDCS and then show it can be used to design efficient algorithms for computing a matching in a variety of computational models.

[Video]

Ruzsa-Szemeredi Graphs (RS graphs henceforth) are a family of extremal graphs with a magical property: they are "locally sparse" and yet "globally dense". More accurately, an (r,t)-RS graph is an edge-disjoint union of t induced matchings, each of size r. Over the years, different constructions of these graphs, with different parameters r,t, have found numerous applications to different areas of TCS. In this talk, we discuss some of these applications to modern techniques in graph algorithms.

[Video]

Consider a graph G = (V, E) that is undergoing a sequence of edge insertions/deletions. We want to design an algorithm that maintains a large matching in this dynamic graph G with small "update time". Here, the "update time" of an algorithm refers to the time it takes to handle the insertion/deletion of an edge in G. Ideally, we would like to ensure that the update time of our algorithm is polylogarithmic in the number of nodes in G. This problem has received considerable attention within the dynamic algorithms community in the past decade. In this talk, I will start with a survey of this topic, and then present an overview of some very recent developments which point to surprising connections between dynamic and sublinear algorithms. 

[Video]

Linear-time algorithms have long been the gold standard of algorithm design. But can we design algorithms that run in time sublinear in the input size? In this talk, I will focus on sublinear time algorithms for the maximum matching problem. I will discuss the recent progress made on this problem both on the algorithmic side and the lower bound side, briefly overview its connections to the dynamic setting, and also mention open problems and future directions.

Based on joint works with Mohammad Roghani and Aviad Rubinstein. 

[Video]

In this talk, I will provide a brief survey of ideas from geometry in designing efficient algorithms for planar and minor-free graphs. The talk focuses on recent developments in embeddings into small treewidth graphs, VC dimension, tree cover, and related problems.  There will be no heavy technical details.  

[Video]

While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious.  We study a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics.  Specifically, a tree cover of a metric space (X, δ) is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees.  The celebrated "Dumbbell Theorem" [ADMSS95] states that any low-dimensional Euclidean space admits a tree cover with O(1) trees and distortion 1+ε, for any fixed 0 < ε < 1.  This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19].  Does the same result hold for planar metrics?  A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics.

In this work, we answer this fundamental question affirmatively.  Specifically, we show that for any given fixed ε, any planar metric can be covered by O(1) trees with distortion 1+ε.  Our result for planar metrics follows from a rather general framework:  First we reduce the problem to constructing tree covers with additive distortion.  Then we introduce the notion of shortcut partition, and draw connection between shortcut partition and additive tree cover.  Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs.  To demonstrate the power of our framework:

We establish additional tree cover results beyond planar metrics; in particular, we present an O(1)-size tree cover with distortion 1+ε for bounded treewidth metrics;

We obtain several algorithmic applications in planar graphs from our tree cover. The grid-like structure is a technical contribution that we believe is of independent interest.  We showcase its applicability beyond tree cover by constructing a simpler and better embedding of planar graphs into O(1)-treewidth graphs with small additive distortion, resolving an open problem in this line of research.

This is a joint work with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. 

[Video]

A popular strategy in TCS research is to define a few canonical "hard problems" for a research area, and then unify open problems and proof strategies by reducing to these hard problems.  Some famous examples include SAT, Unique-Games, many problems in fine-grained complexity, etc.

We will discuss the research area of network design, which includes topics like spanners, distance oracles, hopsets, shortcut sets, etc.  The "girth problem" is essentially the only canonical hard problem for the area.  We will survey the girth problem, and then we will introduce the "bridge girth problem," our new proposal for a second canonical hard problem that captures new corners of the area.  We will leave many open problems and future directions.

Based on joint work with Gary Hoppenworth and Ohad Trabelsi 

[Video]

In this talk, we will see that graph techniques can speed up algorithms for solving multi-commodity flow to high accuracy. This is unexpected as it was shown in [Ita'79 and Ding-Kyng-Zhang'22] that general linear programs without any graph structure can be reduced to multi-commodity flows.

In addition to outlining our improved multi-commodity flow algorithm, we will see open problems and bottlenecks for improving general linear program solvers and how they connect to graph problems. 

[Video]

We study the space requirement for an additive approximation of number of connected components in random order streams through the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds.

While noisy gap cycle counting (NGC) can be solved trivially under a random partition of edges with zero communication when k << log{n}, in this talk we show that when k is a constant factor larger than log{n}, the one-way communication complexity of NGC is Omega(n) bits.

As a corollary of this result, we show that any streaming algorithm that for every eps > 0 estimates the number of connected components of a graph presented in a random order stream to within an eps n additive factor requires 2^{Omega(1/eps)} space.

This is joint work with Sepehr Assadi.

[Video]

We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum degree is larger than the average degree by at most a constant factor. This family of inputs vastly generalizes several families of inputs for which we commonly have improved algorithms, including bounded-degree inputs and random inputs. It also generalizes families of inputs for which we don't usually have faster algorithms, including regular-inputs of arbitrarily high degree and all very dense inputs. We apply our method to achieve breakthroughs in exact algorithms for several central NP-Complete problems including k-SAT, Graph Coloring, and Maximum Independent Set.

Our main tool is the first algorithmic application of the relatively new Hypergraph Container Method (Saxton and Thomason 2015, Balogh, Morris and Samotij 2015). This recent breakthrough, which generalizes an earlier version for graphs (Kleitman and Winston 1982, Sapozhenko 2001), has been used extensively in recent years in extremal combinatorics. An important component of our work is a new generalization of (hyper-)graph containers to Partition Containers.

[Video]

List of Posters:

• Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching, Da Wei (David) Zheng
• Steiner Connectivity Augmentation, Michael Zlatin
• On the Estimation of the Number of Communities for Sparse Networks, Neil Hwang
• (1-ε)-Approximate Maximum Weighted Matching in poly(1/ε, log n) Time in the Distributed and Parallel Settings, Shang-En Huang
• Edge Connectivity Augmentation and Splitting Off, Ruoxu Cen
• Maximal k-Edge-Connected Partition in Weighted Graphs via Local Random Contraction, Chaitanya Nalam
• Motif Cut Sparsifiers, Mikhail Makarov
• Efficient Construction of Directed Hopsets and Parallel Single-Source Shortest Paths, Nairen Cao
• Survivable Network Design Revisited: Group-Connectivity, Qingyun Chen
• Moments, Random Walks, and Limits for Spectrum Approximation, Apoorv Vikram Singh
• Lower Bounds for Exact Hopsets and Shortcut Sets, Gary Hoppenworth
• 1+ε Approximate Dynamic Matching Size in Truly Sublinear Time, Peter Kiss
• Polynomial Ramsey Bounds and 𝜒-boundedness for Weakly Closed Graphs, Vaishali Surianarayanan
• Near-Optimal Deterministic Vertex-Failure Connectivity Oracles, Yaowei Long
• Approximation Algorithms for Network Design in Non-Uniform Fault Models, Rhea Jain
• Graph Reconstruction from Random Subgraphs, Rik Sengupta
• Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set, Shubhang Kulkarni
• Finding a Small Vertex Cut on Distributed Networks, Yonggang Jiang
• Computing Flip Graphs of Highly Non-Convex Polygons, Mattie Ji
• Nearly-linear Time Hypergraph Partitioning via Cut-Matching Games, Antares Chen
• Low-Memory Algorithms for Online Edge Coloring, Manuel Stoeckl
• Streaming Edge Coloring with Asymptotically Optimal Colors, Mohammad Saneian
• Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation, Amir Azarmehr
• Cheeger Inequalities for Vertex Expansion, Directed Graphs and Hypergraphs via Reweighted Eigenvalues, Kam Chuen Tung
• Differentially Private Range Query on Shortest Paths, Chengyuan Deng
• Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance, Chen Wang
• Vantage Point Selection Algorithms for Bottleneck Capacity Estimation, Vikrant Ashvinkumar

In this talk, we will re-examine a classical graph coloring problem through the lens of sublinear algorithms. It is well-known that any graph with maximum degree Delta admits a proper vertex coloring with (Δ+1) colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm that, for instance, examines only a negligible fraction of edges in the graph? 

We present a sparsification theorem for graph coloring that answers this question in the affirmative for several well-studied models of sublinear computation including graph streaming, sublinear time, and massively parallel computation (MPC). The resulting algorithms turn out to be essentially optimal in each of the above-mentioned models.

This is joint work with Sepehr Assadi and Yu Chen.

[Video]

Recent algorithmic results on edge-colourings have been obtained by studying different forms of multi-step Vizing chains. 

We prove new properties of multi-step Vizing chains, which lead to improved algorithms for

• distributed (Δ+1) edge-colouring in the LOCAL model, and

• worst-case dynamic (1+ ε) Δ edge-colouring in the randomised adaptive model

As a consequence of these new insights, the "local Vizing theorem" follows, i.e. that every edge can be coloured with a colour between 0 and the largest degree of an endpoint.

Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a new tool that allows one to reduce problems in the Euclidean space $mathbb{R}^d$ to the line. LSO is a collection of orderings over the points of a metric space, such that every two points are guaranteed to be \`\`close'' in one of the orderings. Later, with Hung Le, we constructed LSO for doubling metrics. Furthermore, we defined two new types of LSO (triangle, left-sided), which allows constructing LSO for many different spaces (e.g. planar graphs).

In this talk we will discuss the various LSO types, and show some applications (specifically to reliable spanners, and labeled nearest neighbor search). 

[Video]

I’ll present the first local edge differentially private (LEDP) algorithms for k-core decomposition, low out-degree ordering, and densest subgraph. Differential privacy is the gold standard for rigorous data privacy guarantees where the traditional central model assumes a trusted curator who takes private input and outputs privatized answers to user queries. However, one major assumption in this model is that the trusted curator always keeps the input private. Unfortunately, such a strong notion of trust is too ideal in today’s world where massive data leaks occur. Thus, in this talk, I’ll discuss private graph algorithms in the local model, where nodes trust no one with their private information. I’ll give a LEDP algorithm whose approximation factor matches that of the currently best non-private distributed algorithm for k-core decomposition with only an poly(log n)/epsilon additive error. I’ll conclude with a discussion of some open questions and potential future work. Joint work with Laxman Dhulipala, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu.

[Video]