Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Detection in the stochastic block model with multiple clusters: proof of
  the achievability conjectures, acyclic BP, and the information-computation
  gap   In a paper that initiated the modern study of the stochastic block model,
Decelle et al., backed by Mossel et al., made the following conjecture: Denote
by $k$ the number of balanced communities, $a/n$ the probability of connecting
inside communities and $b/n$ across, and set
$\mathrm{SNR}=(a-b)^2/(k(a+(k-1)b)$; for any $k \geq 2$, it is possible to
detect communities efficiently whenever $\mathrm{SNR}>1$ (the KS threshold),
whereas for $k\geq 4$, it is possible to detect communities
information-theoretically for some $\mathrm{SNR}<1$. Massouli\'e, Mossel et
al.\ and Bordenave et al.\ succeeded in proving that the KS threshold is
efficiently achievable for $k=2$, while Mossel et al.\ proved that it cannot be
crossed information-theoretically for $k=2$. The above conjecture remained open
for $k \geq 3$.
  This paper proves this conjecture, further extending the efficient detection
to non-symmetrical SBMs with a generalized notion of detection and KS
threshold. For the efficient part, a linearized acyclic belief propagation
(ABP) algorithm is developed and proved to detect communities for any $k$ down
to the KS threshold in time $O(n \log n)$. Achieving this requires showing
optimality of ABP in the presence of cycles, a challenge for message passing
algorithms. The paper further connects ABP to a power iteration method with a
nonbacktracking operator of generalized order, formalizing the interplay
between message passing and spectral methods. For the information-theoretic
(IT) part, a non-efficient algorithm sampling a typical clustering is shown to
break down the KS threshold at $k=4$. The emerging gap is shown to be large in
some cases; if $a=0$, the KS threshold reads $b \gtrsim k^2$ whereas the IT
bound reads $b \gtrsim k \ln(k)$, making the SBM a good study-case for
information-computation gaps.

31
The categories of this paper are: ao-sci
19
The categories of this paper are: eess
37
The categories of this paper are: supr-con
36
The categories of this paper are: cmp-lg
3
The categories of this paper are: physics
29
The categories of this paper are: funct-an
6
The categories of this paper are: astro-ph
18
The categories of this paper are: econ
7
The categories of this paper are: hep-th
0
The categories of this paper are: hep-ph
4
The categories of this paper are: cond-mat
20
The categories of this paper are: acc-phys
17
The categories of this paper are: q-fin
22
The categories of this paper are: chao-dyn
9
The categories of this paper are: nlin
28
The categories of this paper are: alg-geom