Dynamic Matching: Rounding & Sparsification (And New Tools)

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


Duration: 49:28
242 views
5

David Wajc (Technion -- Israel Institute of Technology)
https://simons.berkeley.edu/talks/david-wajc-technion-israel-institute-technology-2023-09-19
Dynamic Graphs and Algorithm Design

To date, adaptive, polylog update time dynamic matching algorithms have been developed yielding (½-ɛ) approximation, and (½+δ)-approximate size estimation. Key to both types of fast algorithms are dynamic rounding of dynamic fractional matching algorithms, using sparsification via (partial) rounding. In this talk I will overview the line of work on rounding via sparsification via rounding. Along the way, I will highlight two new algorithmic primitives robust to adaptive adversaries, and hence of potential use for the design of fast static algorithms: (1) fast almost maximal matching (AMM) algorithms, and (2) optimal dynamic subset sampling algorithms. Time permitting, I will briefly discuss the role AMMs play in the current best polylog time (½+δ)-approximate dynamic matching size estimation algorithms.



Other Videos By Simons Institute for the Theory of Computing


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
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


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