A new set of lecture notes is available here about community detection and recovery in the stochastic block model, including five open problems . As usual, I will document the open problems here, while referring a much more detailed description of the problems on the notes, including description of partial progress.
Open Problem 9.1. (Detection Threshold for SBM for three of more communities)
What is the partial recovery threshold for the Stochastic Block Model on
communities.
Please see the notes for references, history, and more information.
Open Problem 9.2. (Recovery Threshold for SBM for logarithmic many communities)
What is the exact recovery threshold for the Stochastic Block Model with a logarithm number of communities? Both computational and information theoretical.
Please see the notes for references, history, and more information.
Open Problem 9.3. (Tightness of k-median LP)
Is the k-medians Linear Programming relaxation tight even for point clouds coming from generative models that do not have a community structure?
Please see the notes for references, history, and more information.
Open Problem 9.4. (Stability conditions for tightness of k-median LP and k-means SDP)
Can one give conditions for integrality of the k-medians LP or the k-means SDP based on stability type properties (on the fact that the data is “well-explained” by a certain number of clusters)?
Please see the notes for references, history, and more information.
Open Problem 9.5. (Positive PCA tightness)
Is the Semidefinite programming relaxation for the positive Principal Component Analysis problem tight with high probability for Wigner matrices?
Please see the notes for references, history, and more information.
Relax and Conquer 