Dynamic Matching and (Ordered) Ruzsa-Szemerédi Graphs: Towards Constructive Matching Sparsifiers @SimonsInstituteTOC

Simons Institute | Dynamic Matching and (Ordered) Ruzsa-Szemerédi Graphs: Towards Constructive Matching Sparsifiers @SimonsInstituteTOC | Uploaded 1 week ago | Updated 8 hours ago
Soheil Behnezhad (Northeastern University), Alma Ghafari (Northeastern University)
https://simons.berkeley.edu/talks/soheil-behnezhad-northeastern-university-2024-07-30
Sublinear Graph Simplification

Given a graph G, we say a subgraph H of G is a matching sparsifier of G if it preserves large matchings in any induced subgraph of G. In 2012, after formalizing this notion of matching sparsifiers, Goel, Kapralov, and Khanna (GKK) proved existence of a sparse matching sparsifier for any bipartite graph, provided that a certain class of graphs known as Ruzsa-Szemeredi (RS) graphs cannot be too dense. The proof of GKK is non-constructive and does not lead to an efficient (say polynomial time) algorithm for constructing matching sparsifiers.

In this talk, I will describe some approaches to get around this problem and design conditionally fast dynamic algorithms for approximate matchings. My focus will be particularly on the fully dynamic setting where the graph undergoes a sequence of edge insertions and deletions, and the goal is to efficiently maintain an approximate maximum matching of the graph.

Based on:
“Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs” (FOCS’24) joint with Alma Ghafari
“On Regularity Lemma and Barriers in Streaming and Dynamic Matching” (STOC’23) joint with Sepehr Assadi, Sanjeev Khanna, and Huan Li\

Whistle variability and social acoustic interactions in bottlenose dolphins

The Role of Prior Data in Rapid Learning of Motor Skills

Data is as Data Does: The Influence of Computation on Inference

The approximate structure of triangle-free graphs

What neural machinery is needed for language acquisition (Virtual Talk)

Faces, Flukes, Fins, and Flanks: How Multispecies Re-ID Models are Transforming Our Approach to AI..

What Does Machine Learning Have to Offer Mathematics? | Theoretically Speaking

$Sublinear Insights: A Faster (Classical) Algorithm for Edge Coloring Sepehr Assadi (University of Waterloo and Rutgers University) https://simons.berkeley.edu/talks/sepehr-assadi-university-waterloo-rutgers-university-2024-06-20 Extroverted Sublinear Algorithms Vizings theorem states that every graph with maximum degree Delta admits a proper (Delta+1) edge coloring. The state-of-the-art algorithms for finding such a coloring on n-vertex m-edge graphs take O(msqrt(n)) time and date back to the 80s. In this talk, we present a very recent randomized algorithm for finding a Delta+O(log n) coloring in O(m*log(Delta)) time, namely, a near-linear time algorithm for a near-Vizings theorem. This algorithm is inspired by several tools developed in the study of sublinear algorithms. As a corollary of this result and Vizings original approach, we also obtain an O(n^2 log(n)) expected time algorithm for the (Delta+1) edge coloring problem. This is nearly optimal for dense graphs and improves upon the longstanding O(n^{2.5}) bounds of prior work for Vizings theorem in almost four decades. Based on https://arxiv.org/abs/2405.13371 (see also https://arxiv.org/abs/2405.15449 for an independent and concurrent work that obtains an ~O(m*n^{1/3}) time randomized algorithm for Vizings theorem)$

Plenary Talk: Privately Evaluating Untrusted Black-Box Functions