The polynomial-time barrier below the Kesten–Stigum threshold
Statement
Let , let be a probability distribution, and let be a symmetric matrix with nonnegative entries. Let be the diagonal matrix with , and let be the leading eigenvalues of ordered by nonincreasing magnitude. Polynomial-time barrier conjecture. If , then there is no polynomial-time algorithm that can solve weak recovery in a graph drawn from .
This conjecture formalizes the expected computational barrier below the Kesten–Stigum threshold in the general sparse stochastic block model. The source presents it as an open problem; the strict inequality leaves the threshold case itself outside the claim.
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.