Fetching the paper…
Reading the bibliography…
We consider the following general hidden hubs model: an $n \times n$ random matrix $A$ with a subset $S$ of $k$ special rows (hubs): entries in rows outside $S$ are generated from the probability distribution $p_0 \sim N(0,\sigma_0^2)$; for each row in $S$, some $k$ of its entries are generated from $p_1 \sim N(0,\sigma_1^2)$, $\sigma_1>\sigma_0$, and the rest of the entries from $p_0$.
Eigenvalues and graph bisection: An average-case analysis
R. Boppana · 1987
Earlier work this paper cites.
Large cliques elude the metropolis process
M. Jerrum · 1992
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael J. Kearns · 1993
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Expected complexity of graph partitioning problems
L. Kucera · 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.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 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.
The largest eigenvalue of rank one deformation of large wigner matrices
Delphine Féral and Sandrine Péché · 2007
Cited alongside, same era.
A new approach to the planted clique problem
Alan M. Frieze and Ravi Kannan · 2008
Cited alongside, same era.
Random tensors and planted cliques
S. Charles Brubaker and Santosh Vempala · 2009
Cited alongside, same era.
A new probability inequality using typical moments and concentration results
Ravindran Kannan · 2009
Cited alongside, same era.
Detecting high log-densities: an O ( n 1/4 {}^{\mbox{1/4}} ) approximation for densest k -subgraph
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan · 2010
Cited alongside, same era.
Finding hidden cliques in linear time
Uriel Feige and Dorit Ron · 2010
Cited alongside, same era.
Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time
Yash Deshpande and Andrea Montanari · 2015
Later among the works it cites.
Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems
Yash Deshpande and Andrea Montanari · 2015
Later among the works it cites.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Later among the works it cites.
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, and Avi Wigderson · 2015
Later among the works it cites.
On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors
Andrea Montanari, Daniel Reichman, and Ofer Zeitouni · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Finding hidden cliques in linear time with high probability
Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres · 2011
Cited alongside, same era.
Statistical algorithms and a lower bound for planted clique
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao · 2013
Cited alongside, same era.
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin · 2016
Closest in time.
On the integrality gap of degree-4 sum of squares for planted clique
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm · 2016
Closest in time.
Statistical query algorithms for mean estimation and stochastic convex optimization
Vitaly Feldman, Cristobal Guzman, and Santosh Vempala · 2017
Closest in time.