Greg Bodwin - Bridge Girth: A Unifying Notion in Network Design

Greg Bodwin presents "Bridge Girth: A Unifying Notion in Network Design" at the DIMACS Workshop on Modern Techniques in Graph Algorithms held at Rutgers University on June 12, 2023 - June 15, 2023.

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

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.