Is the space complexity of planted clique recovery the same as that of detection?

on YouTube ↗25m

" summary

Asks whether planted clique recovery can match detection in space and gives a near-complete constructive answer: a derandomized, combinatorial algorithm is built that recovers cliques for K ≥ ω(√n · log^{(L)} n) using O(log n) bits, and for K = Θ(√n) it uses about log n · log n* bits. Reduction from detection fails due to insufficiently small error, spectral and SDP approaches are shown infeasible in log space, and the new algorithm succeeds up to the tiny iterated-log gap.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:27What is a 'tractable inference problem?
3. 1:57A case study the planted clique problem
4. 3:28A Brief History
5. 4:58What do we talk about when we talk about computational efficiency?
6. 8:07What is the first thing to study, if we study alternate notions of efficiency?
7. 9:26Planted Clique + Space Complexity
8. 12:40Some easy to see' facts
9. 16:02Can previous polynomial time algorithms help?
10. 22:15Main result
11. 24:11Open Problems