Sketching Algorithms for Max-DICUT and other CSPs

on YouTube ↗01h 00m

" summary

Claims a concrete sketching pipeline: compute the L1 bias via an Indyk-style sketch to get a 2/5 approximation, then refine to 4/9 and 0.485–0.486 approximations in random-order and two-pass models using a snapshot sketch that collapses vertices by bias and uses layered edge sampling; proves matching information‑theoretic lower bounds showing you cannot beat these ratios in o(√n) space for large ranges and extends the bias-vs.-separation dichotomy to general Boolean CSPs with a decidable criterion.

AI-written summary · about

" chapters (14)

1. 0:00Sketching algorithms intro
2. 0:42Constraint satisfaction problems overview
3. 5:00Max-DICUT in streaming
4. 8:11Folklore CSP approx
5. 9:15State of the art max-DICUT
6. 13:54Logspace sketching max-DICUT
7. 15:03Bias-based algorithm
8. 20:434/9 approx and dichotomy
9. 23:58Lower bounds via comm comp
10. 28:57Improved approx in sqrt n space
11. 34:00Snapshot estimation streaming
12. 46:17Generalizations to CSPs
13. 51:40Open questions
14. 59:45Q&A