Sublinear time algorithms for better than 1/2 approximation algorithms for max-cut on expanders

on YouTube ↗32m

" summary

Algorithm works in the adjacency-list query model on bounded-degree d‑regular graphs and distinguishes MC(G) ≥ 1−γ versus ≤ 1/2+γ using random walks, loop‑erased walks and collision counts rather than reconstructing a cut. It runs in about n^{1/2+O(ε)} time, builds a small Gram matrix of collision probabilities and inspects a collision-gram eigenvalue (the rescaled k+c-th eigenvalue) to decide. Guarantee holds for k φ ε-clusterable graphs and relies on a spectral lemma separating eigenvalues near ±1.

AI-written summary · about

" chapters (10)

1. 0:00Sublinear max-cut algorithms
2. 2:12Query model and problem
3. 3:17Max-cut approximation history
4. 6:47Clusterable graphs definition
5. 9:18Challenges with k>1 clusters
6. 12:42Main theorem and algorithm
7. 17:22Spectral claims intuition
8. 22:04Spectral lemma proof
9. 28:05Open problems and future work
10. 29:59Q&A