ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let k∈Z+k\in\mathbb{Z}_+, let p∈(0,1)kp\in(0,1)^k be a probability distribution, and let QQ be a symmetric k×kk\times k matrix with nonnegative entries. Let PP be the diagonal matrix with Pi,i=piP_{i,i}=p_i, and let λ1,λ2\lambda_1,\lambda_2 be the leading eigenvalues of PQPQ ordered by nonincreasing magnitude. Polynomial-time barrier conjecture. If λ22<λ1\lambda_2^2<\lambda_1, then there is no polynomial-time algorithm that can solve weak recovery in a graph GG drawn from SBM(n,p,Q/n)\mathrm{SBM}(n,p,Q/n).

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.