Fetching the paper…
Reading the bibliography…
In the general submatrix detection problem, the task is to detect the presence of a small $k \times k$ submatrix with entries sampled from a distribution $\mathcal{P}$ in an $n \times n$ matrix of samples from $\mathcal{Q}$.
Negative association of random variables with applications
Kumar Joag-Dev and Frank Proschan · 1983
Earlier work this paper cites.
Finding and certifying a large hidden clique in a semirandom graph
Uriel Feige and Robert Krauthgamer · 2000
Earlier work this paper cites.
Spectral partitioning of random graphs
Frank McSherry · 2001
Earlier work this paper cites.
Testing k-wise and almost k-wise independence
Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie · 2007
Earlier work this paper cites.
Finding large average submatrices in high dimensional data
Andrey A Shabalin, Victor J Weigman, Charles M Perou, Andrew B Nobel, et al · 2009
Earlier work this paper cites.
On combinatorial testing problems
Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and Gábor Lugosi · 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
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan · 2010
Earlier work this paper cites.
Finding hidden cliques in linear time
Uriel Feige and Dorit Ron · 2010
Earlier work this paper cites.
Nuclear norm minimization for the planted clique and biclique problems
Brendan PW Ames and Stephen A Vavasis · 2011
Earlier work this paper cites.
Statistical and computational tradeoffs in biclustering
Sivaraman Balakrishnan, Mladen Kolar, Alessandro Rinaldo, Aarti Singh, and Larry Wasserman · 2011
Earlier work this paper cites.
Minimax localization of structural information in large noisy matrices
Mladen Kolar, Sivaraman Balakrishnan, Alessandro Rinaldo, and Aarti Singh · 2011
Earlier work this paper cites.
Everywhere-sparse spanners via dense subgraphs
Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer · 2012
Earlier work this paper cites.
Detection of a sparse submatrix of a high-dimensional noisy matrix
Cristina Butucea and Yuri I Ingster · 2013
Earlier work this paper cites.
Complexity theoretic lower bounds for sparse principal component detection
Quentin Berthet and Philippe Rigollet · 2013
Earlier work this paper cites.
Optimal detection of sparse principal components in high dimension
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Community detection in dense random networks
Ery Arias-Castro, Nicolas Verzelen, et al · 2014
Cited alongside, same era.
Finding hidden cliques in linear time with high probability
Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres · 2014
Cited alongside, same era.
Hidden cliques and the certification of the restricted isometry property
Pascal Koiran and Anastasios Zouzias · 2014
Cited alongside, same era.
Incoherence-optimal matrix completion
Yudong Chen · 2015
Cited alongside, same era.
Asymptotic mutual information for the two-groups stochastic block model
Yash Deshpande, Emmanuel Abbe, and Andrea Montanari · 2015
Achieving exact cluster recovery threshold via semidefinite programming
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2016
Later among the works it cites.
Semidefinite programs for exact recovery of a hidden community
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2016
Later among the works it cites.
Mutual information in rank-one matrix estimation
Florent Krzakala, Jiaming Xu, and Lenka Zdeborová · 2016
Later among the works it cites.
Average-case hardness of rip certification
Tengyao Wang, Quentin Berthet, and Yaniv Plan · 2016
Later among the works it cites.
Statistical and computational trade-offs in estimation of sparse principal components
Tengyao Wang, Quentin Berthet, and Richard J Samworth · 2016
Later among the works it cites.
Minimizing the union: Tight approximations for small set bipartite vertex expansion
Eden Chlamtáč, Michael Dinitz, and Yury Makarychev · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time
Yash Deshpande and Andrea Montanari · 2015
Cited alongside, same era.
Computational lower bounds for community detection on random graphs
Bruce E Hajek, Yihong Wu, and Jiaming Xu · 2015
Cited alongside, same era.
Mmse of probabilistic low-rank matrix estimation: Universality with respect to the output channel
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová · 2015
Cited alongside, same era.
Finding one community in a sparse graph
Andrea Montanari · 2015
Cited alongside, same era.
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
Cited alongside, same era.
Computational barriers in minimax submatrix detection
Zongming Ma and Yihong Wu · 2015
Cited alongside, same era.
Later among the works it cites.
Computational and statistical boundaries for submatrix localization in a large noisy matrix
T Tony Cai, Tengyuan Liang, Alexander Rakhlin, et al · 2017
Later among the works it cites.
Sparse cca: Adaptive estimation and computational barriers
Chao Gao, Zongming Ma, and Harrison H Zhou · 2017
Later among the works it cites.
Information limits for recovering a hidden community
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2017
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2018
Later among the works it cites.
Finding planted subgraphs with few eigenvalues using the schur–horn relaxation
Utkan Onur Candogan and Venkat Chandrasekaran · 2018
Later among the works it cites.
Sherali-adams integrality gaps matching the log-density threshold
E. Chlamtáč and P. Manurangsi · 2018
Later among the works it cites.
Statistical problems with planted structures: Information-theoretical and computational limits
Yihong Wu and Jiaming Xu · 2018
Later among the works it cites.
Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness
Matthew Brennan and Guy Bresler · 2019
Closest in time.