Greg Bodwin wins Best Paper Award at SOSA 2024

Greg Bodwin, assistant professor of Computer Science and Engineering at the University of Michigan, has received a Best Paper Award at the 2024 SIAM Symposium on Simplicity in Algorithms (SOSA) for his research on light graph spanners. His paper titled “An Alternate Proof of Near-Optimal Light Spanners” offers a new proof of light spanners of improved size, allowing for more accurate calculation of the distances between nodes in graphs. 

SOSA is an annual conference organized by the Society for Industrial and Applied Mathematics (SIAM) that is dedicated to advancing simple, elegant algorithms in theoretical computer science. According to SOSA organizers, promoting simplicity in the design of algorithms is vital on many fronts, enabling more straightforward and implementable explanations to complex problems and expanding the accessibility of these solutions to students and practitioners alike.

Bodwin’s paper was recognized with a Best Paper Award due to both its excellence and its importance in advancing light spanners, a type of subgraph that aims to approximate the original distances between nodes while minimizing the total weight of the edges. Light spanners thus minimize cost while preserving the shortest-path distances between nodes, making them highly desirable in the design of networks, distributed systems, and more.

Bodwin’s proof further optimizes our understanding of spanners by demonstrating the tradeoff between spanner lightness (i.e., size) and stretch factor, the amount of stretch or distortion a spanner introduces to a graph. His work is a response to the stretch/lightness tradeoff theorem first introduced by Chechik and Wulff-Nilsen (SODA ’16) and builds on the innovative proof of this theorem by Le and Solomon (SODA ‘23). 

In his paper, Bodwin introduces a new proof of this theorem that includes a direct analysis of the greedy spanner algorithm, which ensures near-optimal tradeoffs between stretch and both lightness and sparsity. It includes improved ε-dependence, enabling more accurate approximation of node distances, while also maintaining simplicity by following the proof structure of the Moore bounds.

In all, Bodwin’s proof constitutes an important contribution to graph theory and theoretical computer science, by improving the accuracy and efficiency of an algorithm that underpins network design.