Fetching the paper…
Reading the bibliography…
Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc.
The rotation of eigenvectors by a perturbation. iii
C. Davis, W.M. Kahan · 1970
Earlier work this paper cites.
The employee party problem
D.W. Matula · 1972
Earlier work this paper cites.
Perturbation bounds in connection with singular value decomposition
P.-Å. Wedin · 1972
Earlier work this paper cites.
Expected behavior of graph coloring algorithms
L. Kučera · 1977
Earlier work this paper cites.
Fast solution of some random NP-hard problems
M.E. Dyer, A.M. Frieze · 1986
Earlier work this paper cites.
Eigenvalues and graph bisection: An average-case analysis
R.B. Boppana · 1987
Earlier work this paper cites.
Graph bisection algorithms with good average case behavior
T.N. Bui, S. Chaudhuri, F.T. Leighton, M. Sipser · 1987
Earlier work this paper cites.
J. Kahn and E. Szemerédi, STOC 1989
1989
Earlier work this paper cites.
Simulated annealing for graph bisection
M. Jerrum, G.B. Sorkin · 1993
Earlier work this paper cites.
Coloring random and semi-random k-colorable graphs
A. Blum, J. Spencer · 1995
Cited alongside, same era.
Matrix computations
G.H. Golub, C.F. Van Loan · 1996
Cited alongside, same era.
A new look at independence
M. Talagrand · 1996
Cited alongside, same era.
A spectral technique for coloring random 3-colorable graphs
N. Alon, N. Kahale · 1997
Cited alongside, same era.
Matrix analysis
R. Bhatia · 1997
Cited alongside, same era.
Finding a large hidden clique in a random graph
N. Alon, M. Krivelevich, B. Sudakov · 1998
Cited alongside, same era.
Concentration
C. McDiarmid · 1998
Cited alongside, same era.
Algorithms for graph partitioning on the planted partition model
A. Condon, R.M. Karp · 2001
Later among the works it cites.
Spectral partitioning of random graphs
F. McSherry · 2001
Later among the works it cites.
U. Feige and E. Ofek, Spectral techniques applied to sparse random graphs,
2005
Later among the works it cites.
Spectral norm of random matrices
V. Vu · 2007
Later among the works it cites.
Spectral analysis of large dimensional random matrices
Z. Bai, J.W. Silverstein · 2009
Later among the works it cites.
Spectral algorithms
R. Kannan, S. Vempala · 2009
Later among the works it cites.
Finding hidden cliques in linear time
U. Feige, D. Ron · 2010
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Finding and certifying a large hidden clique in a semirandom graph
U. Feige, R. Krauthgamer · 2000
Cited alongside, same era.
Spectral analysis of data
Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia · 2001
Cited alongside, same era.
Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time
Y. Deshpande, A. Montanari
Cited in the paper.
Later among the works it cites.
Finding hidden cliques in linear time with high probability
Y. Dekel, O. Gurel-Gurevich, Y. Peres · 2011
Later among the works it cites.
R. Xu and D. Wunsch, Clustering, Wiley 2014
2014
Closest in time.