Decelle–Krzakala–Moore–Zdeborová Potts-model conjecture for k communities
Statement
Let be the planted partition model with communities, where . Let be a threshold depending only on . Decelle–Krzakala–Moore–Zdeborová's Potts-model conjecture. For any , there exists such that
implies that the clustering problem cannot be solved;
implies that it is solvable but not in polynomial time; and
implies that it can be solved in polynomial time. When , , so the intermediate case does not occur; when , . This conjecture predicts distinct information-theoretic and computational transitions for the multi-community model, motivated by phase transitions in the Potts model on trees. The source notes that non-reconstruction results are less precise for and gives no resolution of the conjecture.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.