Fetching the paper…
Reading the bibliography…
This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph $\mathcal{G}(N,q)$, where the edge probability within the community exceeds $q$ by a constant factor.
Large cliques elude the metropolis process
M. Jerrum · 1992
Earlier work this paper cites.
Expected complexity of graph partitioning problems
L. Kučera · 1995
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.
Balls and bins: A study in negative dependence
D. Dubhashi and D. Ranjan · 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.
Hiding cliques for cryptographic security
A. Juels and M. Peinado · 2000
Earlier work this paper cites.
Spectral partitioning of random graphs
F. McSherry · 2001
Earlier work this paper cites.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
M. Mitzenmacher and E. Upfal · 2005
Earlier work this paper cites.
Testing k k -wise and almost k k -wise independence
N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie · 2007
Earlier work this paper cites.
Public-key cryptography from different assumptions
B. Applebaum, B. Barak, and A. Wigderson · 2010
Earlier work this paper cites.
Computational complexity and information asymmetry in financial products
S. Arora, B. Barak, M. Brunnermeier, and R. Ge · 2010
Earlier work this paper cites.
Detecting high log-densities: An o ( n 1 / 4 ) o(n^{1/4}) approximation for densest k k -subgraph
A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan · 2010
Earlier work this paper cites.
Finding hidden cliques in linear time with high probability
Y. Dekel, O. Gurel-Gurevich, and Y. Peres · 2010
Earlier work this paper cites.
Finding hidden cliques in linear time
U. Feige and D. Ron · 2010
Cited alongside, same era.
Community detection in graphs
S. Fortunato · 2010
Cited alongside, same era.
Inapproximabilty of densest κ \kappa -subgraph from average case hardness
N. Alon, S. Arora, R. Manokaran, D. Moshkovitz, and O. Weinstein · 2011
Cited alongside, same era.
Nuclear norm minimization for the planted clique and biclique problems
B. P. Ames and S. A. Vavasis · 2011
Cited alongside, same era.
Statistical and computational tradeoffs in biclustering
S. Balakrishnan, M. Kolar, A. Rinaldo, A. Singh, and L. Wasserman · 2011
Cited alongside, same era.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova · 2011
Cited alongside, same era.
Detection of a sparse submatrix of a high-dimensional noisy matrix
C. Butucea and Y. I. Ingster · 2013
Later among the works it cites.
Computational and statistical tradeoffs via convex relaxation
V. Chandrasekaran and M. I. Jordan · 2013
Later among the works it cites.
Statistical algorithms and a lower bound for detecting planted cliques
V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao · 2013
Later among the works it cites.
Community detection thresholds and the weak Ramanujan property
L. Massoulié · 2013
Later among the works it cites.
A proof of the block model threshold conjecture
E. Mossel, J. Neeman, and A. Sly · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
How hard is it to approximate the best Nash equilibrium?
E. Hazan and R. Krauthgamer · 2011
Cited alongside, same era.
Minimax localization of structural information in large noisy matrices
M. Kolar, S. Balakrishnan, A. Rinaldo, and A. Singh · 2011
Cited alongside, same era.
A simple decoupling inequality in probability theory
R. Vershynin · 2011
Cited alongside, same era.
Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time
Y. Deshpande and A. Montanari · 2012
Cited alongside, same era.
Stochastic block models and reconstruction
E. Mossel, J. Neeman, and A. Sly · 2012
Cited alongside, same era.
Robust convex relaxation for the planted clique and densest k k -subgraph problems
B. P. Ames · 2013
Cited alongside, same era.
N. Verzelen and E. Arias-Castro · 2013
Later among the works it cites.
Exact recovery in the stochastic block model
E. Abbe, A. S. Bandeira, and G. Hall · 2014
Closest in time.
Community detection in dense random networks
E. Arias-Castro and N. Verzelen · 2014
Closest in time.
Y. Chen and J. Xu · 2014
Closest in time.
Achieving exact cluster recovery threshold via semidefinite programming
B. Hajek, Y. Wu, and J. Xu · 2014
Closest in time.
Consistency thresholds for binary symmetric block models
E. Mossel, J. Neeman, and A. Sly · 2014
Closest in time.
Jointly clustering rows and columns of binary matrices: Algorithms and trade-offs
J. Xu, R. Wu, K. Zhu, B. Hajek, R. Srikant, and L. Ying · 2014
Closest in time.
Computational barriers in minimax submatrix detection
Z. Ma and Y. Wu · 2015
Closest in time.