CSE theory researchers co-author seven papers at IEEE FOCS 2022

Seven papers authored or co-authored by CSE researchers at the University of Michigan were accepted to appear at the 2022 IEEE Symposium on Foundations of Computer Science (FOCS 2022), one of the two leading general theoretical computing conferences in the world. Seven U-M researchers identified new bounds on algorithms critical to data analytics, broke barriers in graph theory, and tackled algorithmic efficiency in a variety of other areas.

Learn more about the projects:

Balanced Allocations: The Heavily Loaded Case with Deletions

Nikhil Bansal (University of Michigan), William Kuszmaul (MIT)

Randomized balls-into-bins processes serve as a useful abstraction for studying load-balancing problems, with applications such as scheduling, distributed systems, and data structures. This work shows that previously demonstrated bounds in some classes of these problems don’t hold in the dynamic setting, and proves new upper and lower bounds for the dynamic heavily-loaded case.

Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time

Amir Abboud (Weizmann Institute of Science), Robert Krauthgamer (Weizmann Institute of Science), Jason Li (UC Berkeley), Debmalya Panigrahi (Duke University), Thatchaphol Saranurak (University of Michigan), Ohad Trabelsi (University of Michigan)

This paper breaks a longstanding barrier in graph theory by cutting the All-Pairs Max-Flow problem on general, weighted graphs from cubic time to Õ(n²) time. The authors also establish a counter-intuitive separation: all-pairs max-flows are strictly easier to compute than all-pairs shortest-paths. Their algorithm produces a cut-equivalent tree, known as the Gomory-Hu tree, from which the max-flow value for any pair can be retrieved in near-constant time.

Correlation Clustering with Sherali-Adams

Vincent Cohen-Addad (Google Research), Euiwoong Lee (University of Michigan), Alantha Newman (Laboratoire G-SCOP (CNRS, Grenoble-INP))

Clustering is a central problem in unsupervised machine learning and data mining. Given a dataset and information regarding the similarity of pairs of elements, a “good” clustering is a partition of the elements into groups such that similar elements belong to the same group, while dissimilar elements belong to different groups. This paper answers a major open question in the area of clustering, demonstrating an algorithm that achieves a previously unreachable approximation factor for correlation clustering.

Deterministic Small Vertex Connectivity in Almost Linear Time

Thatchaphol Saranurak (University of Michigan), Sorrachai Yingchareonthawornchai (Aalto University)

This paper demonstrates the use of expander decomposition and vertex sparsifiers for deterministically computing vertex connectivity in almost-linear time when the connectivity is constant. This breaks the 50-year-old quadratic bound.

Fitting Metrics and Ultrametrics with Minimum Disagreements

Vincent Cohen-Addad (Google), Chenglin Fan (Sorbonne Université, Paris, France), Euiwoong Lee (University of Michigan), Arnaud de Mesmay (CNRS, LIGM, Université Gustave Eiffel)

This study presents an exponentially improved approximation algorithm for the metric violation distance problem, which involves fitting pairwise data to a metric data that satisfies the requirements of a metric space. The problem is useful in applications including data analysis, machine learning, and optimization.

Near-Optimal Deterministic Vertex-Failure Connectivity Oracles

Yaowei Long (University of Michigan), Thatchaphol Saranurak (University of Michigan)

This paper revisits the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-understood. The authors essentially settle the complexity of this problem by showing a new data structure whose space, preprocessing time, update time, and query time are simultaneously optimal up to sub-polynomial factors assuming popular conjectures. Moreover, the data structure is deterministic.

New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

Greg Bodwin (University of Michigan), Gary Hoppenworth (University of Michigan)

A basic question arising in robotics, circuit design, distributed algorithms, and many other areas of computer science is to compress a graph metric into small space while approximately preserving its shortest path distances. For an input graph, an additive spanner is a sparse subgraph whose shortest paths match those of the input graph up to small additive error. This paper proves two new lower bounds in the area of additive spanners.