Fetching the paper…
Reading the bibliography…
We study a semidefinite programming (SDP) relaxation of the maximum likelihood estimation for exactly recovering a hidden community of cardinality $K$ from an $n \times n$ symmetric data matrix $A$, where for distinct indices $i,j$, $A_{ij} \sim P$ if $i, j$ are both in the community and $A_{ij} \sim Q$ otherwise, for two known probability distributions $P$ and $Q$.
On the application of the Borel-Cantelli lemma
K.-L. Chung and P. Erdös · 1952
Earlier work this paper cites.
Reducibility among combinatorial problems
R. Karp · 1972
Earlier work this paper cites.
Stochastic blockmodels: First steps
P. W. Holland, K. B. Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix
Z. Bai and Y. Yin · 1988
Earlier work this paper cites.
Finding a large hidden clique in a random graph
N. Alon, M. Krivelevich, and B. Sudakov · 1998
Earlier work this paper cites.
Finding and certifying a large hidden clique in a semirandom graph
U. Feige and R. Krauthgamer · 2000
Earlier work this paper cites.
Local operator theory, random matrices and Banach spaces
K. Davidson and S. Szarek · 2001
Earlier work this paper cites.
Spectral partitioning of random graphs
F. McSherry · 2001
Earlier work this paper cites.
Order Statistics
H. David and H. Nagaraja · 2003
Earlier work this paper cites.
The probable value of the Lovász–Schrijver relaxations for maximum independent set
U. Feige and R. Krauthgamer · 2003
Earlier work this paper cites.
Convex Optimization
S. Boyd and L. Vandenberghe · 2004
Earlier work this paper cites.
Some estimates of norms of random matrices
R. Latała · 2005
Earlier work this paper cites.
Spectral norm of random matrices
V. H. Vu · 2007
Earlier work this paper cites.
Finding large average submatrices in high dimensional data
A. A. Shabalin, V. J. Weigman, C. M. Perou, and A. B. Nobel · 2009
Earlier work this paper cites.
Minimax localization of structural information in large noisy matrices
M. Kolar, S. Balakrishnan, A. Rinaldo, and A. Singh · 2011
Cited alongside, same era.
Topics in random matrix theory
T. Tao · 2012
Cited alongside, same era.
Concentration inequalities: A nonasymptotic theory of independence
S. Boucheron, G. Lugosi, and P. Massart · 2013
Cited alongside, same era.
A complete proof of universal inequalities for the distribution function of the binomial law
A. M. Zubkov and A. A. Serov · 2013
Cited alongside, same era.
Sharp nonasymptotic bounds on the norm of random matrices with independent entries
A. S. Bandeira and R. van Handel · 2014
Cited alongside, same era.
Achieving exact cluster recovery threshold via semidefinite programming: Extensions
B. Hajek, Y. Wu, and J. Xu · 2015
Later among the works it cites.
Computational lower bounds for community detection on random graphs
B. Hajek, Y. Wu, and J. Xu · 2015
Later among the works it cites.
Information limits for recovering a hidden community
B. Hajek, Y. Wu, and J. Xu · 2015
Later among the works it cites.
Recovering a hidden community beyond the spectral limit in O ( | E | log ∗ | V | ) O(|E|\log^{*}|V|) time
B. Hajek, Y. Wu, and J. Xu · 2015
Later among the works it cites.
Submatrix localization via message passing
B. Hajek, Y. Wu, and J. Xu · 2015
Later among the works it cites.
SoS and planted clique: Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four
S. B. Hopkins, P. K. Kothari, and A. Potechin · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Y. Chen and J. Xu · 2014
Cited alongside, same era.
Achieving exact cluster recovery threshold via semidefinite programming
B. Hajek, Y. Wu, and J. Xu · 2014
Cited alongside, same era.
Sharp performance bounds for graph clustering via convex optimization
R. K. Vinayak, S. Oymak, and B. Hassibi · 2014
Cited alongside, same era.
Multisection in the stochastic block model using semidefinite programming
N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla · 2015
Cited alongside, same era.
Random Laplacian matrices and convex relaxations
A. Bandeira · 2015
Cited alongside, same era.
Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
C. Butucea, Y. Ingster, and I. Suslina · 2015
Cited alongside, same era.
Computational and statistical boundaries for submatrix localization in a large noisy matrix
T. T. Cai, T. Liang, and A. Rakhlin · 2015
Cited alongside, same era.
Later among the works it cites.
Do semidefinite relaxations solve sparse PCA up to the information limit?
R. Krauthgamer, B. Nadler, and D. Vilenchik · 2015
Later among the works it cites.
Concentration and regularization of random graphs
C. M. Le and R. Vershynin · 2015
Later among the works it cites.
Computational barriers in minimax submatrix detection
Z. Ma and Y. Wu · 2015
Later among the works it cites.
Sum-of-squares lower bounds for planted clique
R. Meka, A. Potechin, and A. Wigderson · 2015
Later among the works it cites.
Finding one community in a sparse random graph
A. Montanari · 2015
Later among the works it cites.
Semidefinite programs on sparse random graphs
A. Montanari and S. Sen · 2015
Later among the works it cites.
A semidefinite program for unbalanced multisection in the stochastic block model
W. Perry and A. Wein · 2015
Later among the works it cites.
Tight lower bounds for planted clique in the degree-4 SOS program
P. Raghavendra and T. Schramm · 2015
Later among the works it cites.