10 Lectures and 42 Open Problems — Recovery Threshold for SBM for logarithmic many communities

Definitions and mathematical statement

A stochastic block model on $n$ labelled vertices has hidden community labels $\sigma\in\{1,\ldots,k\}^n$ and, conditional on those labels, independent undirected edges with probabilities $Q_{\sigma_i,\sigma_j}$ for a symmetric matrix $Q\in[0,1]^{k\times k}$. The common equal-size symmetric specialization has within-community probability $p$ and between-community probability $q$, but that specialization and its parameters are not supplied in the source.

An estimator achieves exact recovery if its output equals $\sigma$ up to permutation of community labels with probability tending to one as $n\to\infty$, under the intended label and graph distribution. Information-theoretic recovery allows unrestricted estimators; computational recovery asks for an algorithm with the specified efficiency, conventionally polynomial time in $n$.

Problem. Determine the sharp information-theoretic and computational exact-recovery thresholds when the number of communities grows logarithmically with $n$. This requires a parameterized model and asymptotic regime for community sizes and edge probabilities. The source says a logarithm number, whereas its research summary uses $k=O(\log n)$; logarithmic order $k=\Theta(\log n)$ is a distinct, more specific regime. Neither interpretation is silently substituted for the other.

The supplied summary reports both thresholds known, attributes polynomial-time spectral or semidefinite-programming recovery to Abbe--Bandeira--Hall and Abbe--Sandon, and describes a signal threshold as $(\log n)/(\log k)$ times a model-dependent constant. It never defines that signal or the constant and gives no theorem hypotheses for growing $k$. Therefore this formula cannot serve as an exact numerical threshold, and the reported solved status is retained as an attribution pending model-specific verification.

Short English statement

Find sharp feasibility and efficient-algorithm thresholds for recovering all SBM communities when their number grows logarithmically. The graph parameters, size assumptions, and precise growth regime are missing.

Sources

• Afonso S. Bandeira, 42 Open Problems in Data Science (source list labelled 2016), Open Problem 9.2, author blog https://afonsobandeira.wordpress.com/2015/11/28/10l42psbm/; HTML extraction, accessed 2026-07-29. The registry gives proposed year 2015.
• Abbe--Bandeira--Hall and Abbe--Sandon, as attributed by the research summary for exact-recovery thresholds and efficient algorithms. No titles, dates, theorem numbers, or bibliographic identifiers are supplied.
• Local registry data/unsolvedmath/problems.json, permanent ID $2800902$, source code catalogue entry, 10 Lectures and 42 Open Problems --- Recovery Threshold for SBM for logarithmic many communities. The record labels this solved and SOLVED-IN-LITERATURE, with NEEDS_REVIEW source-status and rights qualifications.