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

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


Duration: 46:40
404 views
10

Soheil Behnezhad (Northeastern University)
https://simons.berkeley.edu/talks/soheil-behnezhad-northeastern-university-2023-09-22
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 continue to discuss algorithms for estimating the size of maximum matching. However, I will focus on lower bounds this time. Specifically, I will provide an overview of a recent technique based on correlation decay that leads to super-linear (in the number of nodes) lower bounds for estimating the size of maximum matching provided that the desired approximation is larger than 2/3.

Based on joint works with Mohammad Roghani and Aviad Rubinstein.

https://arxiv.org/abs/2211.15843



Other Videos By Simons Institute for the Theory of Computing


2023-09-27Distributed Graph Techniques in the MPC Model
2023-09-27Massively Parallel Evaluation of Relational Queries II
2023-09-27Massively Parallel Evaluation of Relational Queries I
2023-09-26Intermediate Relational Algorithm Design
2023-09-26Introduction to Relational Algorithms
2023-09-25Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
2023-09-25Fine Grained Complexity
2023-09-25Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II
2023-09-22Accelerating the Multiplicative-Weights Framework for Graph Linear Programs
2023-09-22Parallel Batch-Dynamic Graph Algorithms
2023-09-22Recent Progress on Sublinear Time Algorithms for Maximum Matching: Lower Bounds
2023-09-21Faster High Accuracy Multi-Commodity Flows via Graph Techniques
2023-09-21Minimum Isolating Cuts: A New Tool for Solving Minimum Cut Problems
2023-09-21On Dynamic Graph Approximations: The case of j-Trees
2023-09-21On Engineering Dynamic Graph Algorithms
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


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