Workshop Program

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. 

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. 

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

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. 

We plan to play a version of Salad Bowl with CS Theory words/terms. Nicole Wein will be leading the session. More details coming soon. 

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.

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.

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.

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. 

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. 

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. 

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 

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.

The list of accepted posters can be found here. The food for the reception will be in CoRE 401 and the posters will be displayed all around the DIMACS U-shaped hallway on the 4th floor of CoRE. 

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.

Use this sheet for signing up to present open problems. Based on the number of sign-ups, we shall decide the time allotted to each problem. If there is still time left after the enrolled presentations, we can have ad-hoc presentations. 

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