Shaving logs by weighing coins

on YouTube ↗39m

" summary

Claims an order-n expected cut-query algorithm to find a spanning forest (shaving the standard n log n), using coin-weighing / Lindström–Cantor–Mills constructions plus BIS (one-bit) queries and sparse-graph learning primitives. Key ingredients: Grebinski–Kucherov style reduction from matching to coin-weighing, randomized Borůvka-style phases with careful sampling instead of degree bucketing, and a Las Vegas-style check to keep zero error in expectation. Works for unweighted graphs; weighted case needs extra sampling care but the order-n expectation goal is achieved.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 1:23Graph connectivity via cuts
3. 7:32Lower bounds for one-bit queries
4. 10:25Coin weighing basics
5. 15:30Learning matchings with cuts
6. 21:57Learning sparse graphs
7. 26:12Boruvka spanning forest
8. 28:42Weighted graphs sampling
9. 31:58Spanning forests in O(n)
10. 34:07Open problems