The Power of Hierarchies for Detecting Hidden Structures

on YouTube ↗01h 07m

" summary

Proves that degree-D sum-of-squares power to distinguish planted vs. null instances reduces to a concrete spectral test: build a low-degree matrix polynomial and check its top eigenvalue. Uses a mechanical construction called pseudo-calibration that projects the planted-solution-weighted density to low-degree and then finds a PSD, high-entropy proxy; if SOS refutes the null then the resulting low-degree spectral distinguisher has much larger expectation on the planted model. Applies to planted clique, community detection and CSPs; guarantees are in expectation and depend on a subsampling parameter linking D to instance sparsity.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:20Title
3. 6:00Indistinguishable distributions
4. 17:00Two distributions
5. 18:25Expectations
6. 20:00Lowdegree matrix distinguisher
7. 28:25System of polynomial equations
8. 33:25Robust inference property
9. 34:30Plant leak case
10. 38:10Robust inference
11. 40:15polynomial system
12. 44:25random drilling
13. 45:02intensive PCA
14. 45:43main theorem
15. 53:57pseudocalibration