Perfect Matchings

on YouTube ↗32m

" summary

Covers algorithms and complexity questions around perfect matchings in graphs, discussing techniques from combinatorics and theoretical computer science used to find or count perfect matchings and to understand their computational hardness; mentions tools and results relevant to matchings (e.g., polynomial-time algorithms, randomized methods, and complexity-theoretic perspectives).

AI-written summary · about

" chapters (9)

1. 0:00Start
2. 4:11Perfect Matchings
3. 7:00PMs & symbolic matrices Edmonds 67
4. 15:45FindPM ENC ? Sharan-W 96
5. 19:19Approximating the Permanent
6. 21:25Scaling algorithm LSW 01
7. 24:45Quantum scaling alg Gurvits 04
8. 27:09Matching "in the dark" Gurvits '04
9. 28:23What does Gurvits alg do?? [Garg-Gurvits-Olivera-W '15]