Sharp Threshold for the Planted Matching Problem

on YouTube ↗11m

" summary

Establishes a sharp statistical threshold λ = 4 for exact recovery in the planted matching model, proves the minimum-weight perfect matching is information-theoretically optimal, and extends to arbitrary true/fake edge distributions P,Q on graphs with average degree D where the limit depends only on D and the Bhattacharyya coefficient. Shows near-critical error fraction scales like exp(-c/√ε) when λ = 4−ε. Standard second-moment and local-structure approaches fail, so the proof uses new posterior-mass analysis; polynomial-time Hungarian algorithm attains the threshold (no computational gap).

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 1:20Background
3. 2:50Natural Solution
4. 4:49Analysis
5. 7:59Planted Problems
6. 9:01Computational Gaps

" related talks

• 40mTesting Correlation of Unlabeled Random GraphsJiaming Xu · Computational Phase Transitions (Simons Institute, 2020)
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 54mExact Matching Of Random Graphs With Constant CorrelationCheng Mao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 25mFundamental Limit of Community Detection in Stochastic Block ModelsEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis