Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
summary
Claims the pass complexity is settled: an algorithm uses log log n passes and n·polylog n space to produce a constant‑approximate matching (roundable to 1+ε), and a matching lower bound shows any constant approximation needs log log n passes under n·polylog n space. Key tools are randomized greedy MIS and a new fractional construction that writes local star weights on edges then rounds to an integral matching; it runs and analyzes successfully.
AI-written summary · about
chapters (12)
- 0:00Dynamic graph stream matchings
- 1:09Problem setup and streaming model
- 4:18Multi-pass algorithms and approximation
- 7:13Pass complexity bounds
- 9:08Techniques and MIS connection
- 11:58Fractional matchings recap
- 13:47MIS to matchings link
- 16:20Handling deletions
- 18:31Fractional matchings in practice
- 21:45MIS to matchings reduction
- 22:49Open problems
- 27:13Q&A
related talks
01h 02mFine-Grained Counting Complexity I
01h 02mFine-Grained Counting Complexity II
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
27mAll-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
23mWorst-Case to Expander-Case Reductions
01h 04mLossy Kernelization