Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=cHf-n3co6bw


Duration: 1:00:37
416 views
7

Soheil Behnezhad (Northeastern University)
https://simons.berkeley.edu/talks/soheil-behnezhad-northeastern-university-2023-09-19
Dynamic Graphs and Algorithm Design

Linear-time algorithms have long been the gold standard of algorithm design. But can we design algorithms that run even faster in time sublinear in the input size? In this talk, I will focus on such algorithms for estimating the size of maximum matching in graphs.

I will start by motivating the problem by showing how the recent progress on the sublinear time maximum matching problem has led to the resolution of a longstanding open problem in dynamic graphs. I will then present an overview of some existing algorithms for sublinear time matching.

Based mainly on

https://arxiv.org/abs/2207.07607

https://arxiv.org/abs/2106.02942



Other Videos By Simons Institute for the Theory of Computing


2023-09-21Dynamic Graphs on the GPU
2023-09-20Dynamic PageRank: Additive Error and Batch Recomputation
2023-09-20Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
2023-09-20Online List Labeling: Breaking the log^2 n Barrier
2023-09-20Practical Dynamic Graph Algorithms: Data Structures and Connections Between Models
2023-09-20Decremental Shortest Paths against an Adaptive Adversary
2023-09-19Dynamic Matching: Rounding & Sparsification (And New Tools)
2023-09-19Parallel Batch-Dynamic Graph Representations
2023-09-19Dynamic Algorithms for 𝑘-center on Graphs
2023-09-19A Blackbox Reduction for Adaptive Adversaries using Differential Privacy
2023-09-19Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds
2023-09-18Parallelism in Dynamic Graph Algorithms
2023-09-18Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy
2023-09-18Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models
2023-09-18Approximating Edit Distance in the Fully Dynamic Model
2023-09-18Lightning Talks
2023-09-12Dynamic Graph Algorithms: What We Know and What We Don’t | Richard M. Karp Distinguished Lecture
2023-09-08Probabilistic and Logical Circuits for Tractable Causal Reasoning
2023-09-08Probabilistic Reasoning and Learning for Trustworthy AI
2023-09-08Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime
2023-09-08Massively Parallel Join Algorithms


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Dynamic Graphs and Algorithm Design
Soheil Behnezhad