Fetching the paper…
Reading the bibliography…
This paper studies the minimax detection of a small submatrix of elevated mean in a large matrix contaminated by additive Gaussian noise.
Rényi, A.A. (1959). On the dimension and entropy of probability distributions. Acta Math. Acad. Sci. Hungar. 10 193–215 (unbound insert)
1959
Earlier work this paper cites.
Strassen, V.V. (1965). The existence of probability measures with given marginals. Ann. Math. Statist. 36 423–439
1965
Earlier work this paper cites.
Csiszár, I.I. (1967). Information-type measures of difference of probability distributions and indirect observations. Studia Sci. Math. Hungar. 2 299–318
1967
Earlier work this paper cites.
Knuth, Donald E.D. E. (1969). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA
1969
Earlier work this paper cites.
Le Cam, LucienL. (1986). Asymptotic Methods in Statistical Decision Theory. Springer, New York
1986
Earlier work this paper cites.
Kuvcera, LudvekL. (1992). A generalized encryption scheme based on random graphs. In Graph-Theoretic Concepts in Computer Science (Fischbachau, 1991). Lecture Notes in Computer Science 570 180–186. Springer, Berlin
1991
Earlier work this paper cites.
Jerrum, MarkM. (1992). Large cliques elude the Metropolis process. Random Structures Algorithms 3 347–359
1992
Earlier work this paper cites.
Kuvcera, LudvekL. (1995). Expected complexity of graph partitioning problems. Discrete Appl. Math. 57 193–212
1995
Earlier work this paper cites.
Bhatia, RajendraR. (1997). Matrix Analysis. Graduate Texts in Mathematics 169. Springer, New York
1997
Earlier work this paper cites.
Alon, NogaN., Krivelevich, MichaelM. andSudakov, BennyB. (1998). Finding a large hidden clique in a random graph. In Proceedings of the Ninth Annual ACM–SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998) 594–598. ACM, New York
1998
Earlier work this paper cites.
Feige, UrielU. andKrauthgamer, RobertR. (2000). Finding and certifying a large hidden clique in a semirandom graph. Random Structures Algorithms 16 195–208
2000
Earlier work this paper cites.
Juels, AriA. andPeinado, MarcusM. (2000). Hiding cliques for cryptographic security. Des. Codes Cryptogr. 20 269–280
2000
Earlier work this paper cites.
Shiryaev, A. N.A. N. andSpokoiny, V. G.V. G. (2000). Statistical Experiments and Decisions: Asymptotic Theory. Advanced Series on Statistical Science & Applied Probability 8. World Scientific, River Edge, NJ
2000
Earlier work this paper cites.
Cover, Thomas M.T. M. andThomas, Joy A.J. A. (2006). Elements of Information Theory, 2nd ed. Wiley, Hoboken, NJ
2006
Earlier work this paper cites.
Alon, NogaN., Andoni, AlexandrA., Kaufman, TaliT., Matulef, KevinK., Rubinfeld, RonittR. andXie, NingN. (2007). Testing k k -wise and almost k k -wise independence. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing 496–505. ACM, New York
2007
Cited alongside, same era.
Arora, SanjeevS. andBarak, BoazB. (2009). Computational Complexity: A Modern Approach. Cambridge Univ. Press, Cambridge
2009
Cited alongside, same era.
Candès, Emmanuel J.E. J. andRecht, BenjaminB. (2009). Exact matrix completion via convex optimization. Found. Comput. Math. 9 717–772
2009
Cited alongside, same era.
Koshy, ThomasT. (2009). Catalan Numbers with Applications. Oxford Univ. Press, Oxford
2009
Cited alongside, same era.
Shabalin, Andrey A.A. A., Weigman, Victor J.V. J., Perou, Charles M.C. M. andNobel, Andrew B.A. B. (2009). Finding large average submatrices in high dimensional data. Ann. Appl. Stat. 3 985–1012
2012
Later among the works it cites.
2013
Closest in time.
Berthet, Q.Q. andRigollet, P.P. (2013). Complexity theoretic lower bounds for sparse principal component detection. Journal of Machine Learning Research: Workshop and Conference Proceedings 30 1–21
2013
Closest in time.
Berthet, QuentinQ. andRigollet, PhilippeP. (2013). Optimal detection of sparse principal components in high dimension. Ann. Statist. 41 1780–1815
2013
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2009
Cited alongside, same era.
Addario-Berry, LouigiL., Broutin, NicolasN., Devroye, LucL. andLugosi, GáborG. (2010). On combinatorial testing problems. Ann. Statist. 38 3063–3092
2010
Cited alongside, same era.
Applebaum, BennyB., Barak, BoazB. andWigderson, AviA. (2010). Public-key cryptography from different assumptions. In STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing 171–180. ACM, New York
2010
Cited alongside, same era.
Feige, UrielU. andRon, DoritD. (2010). Finding hidden cliques in linear time. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’10) 189–203. Assoc. Discrete Math. Theor. Comput. Sci., Nancy
2010
Cited alongside, same era.
Rossman, BenjaminB. (2010). Average-case complexity of detecting cliques. Ph.D. thesis, Massachusetts Institute of Technology
2010
Cited alongside, same era.
Ames, Brendan P. W.B. P. W. andVavasis, Stephen A.S. A. (2011). Nuclear norm minimization for the planted clique and biclique problems. Math. Program. 129 69–89
2011
Cited alongside, same era.
Balakrishnan, S.S., Kolar, M.M., Rinaldo, A.A., Singh, A.A. andWasserman, L.L. (2011). Statistical and computational tradeoffs in biclustering. In NIPS 2011 Workshop on Computational Trade-Offs in Statistical Learning
2011
Cited alongside, same era.
Dekel, YaelY., Gurel-Gurevich, OriO. andPeres, YuvalY. (2011). Finding hidden cliques in linear time with high probability. In ANALCO11—Workshop on Analytic Algorithmics and Combinatorics 67–75. SIAM, Philadelphia, PA
2011
Cited alongside, same era.
2013
Closest in time.
Chandrasekaran, VenkatV. andJordan, Michael I.M. I. (2013). Computational and statistical tradeoffs via convex relaxation. Proc. Natl. Acad. Sci. USA 110 E1181–E1190
2013
Closest in time.
2013
Closest in time.
Feldman, VitalyV., Grigorescu, ElenaE., Reyzin, LevL., Vempala, Santosh S.S. S. andXiao, YingY. (2013). Statistical algorithms and a lower bound for detecting planted cliques. In STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing 655–664. ACM, New York
2013
Closest in time.
2013
Closest in time.
2013
Closest in time.
Sun, XingX. andNobel, Andrew B.A. B. (2013). On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix. Bernoulli 19 275–294
2013
Closest in time.
2013
Closest in time.
Koiran, PascalP. andZouzias, AnastasiosA. (2014). Hidden cliques and the certification of the restricted isometry property. IEEE Trans. Inform. Theory 60 4999–5006
2014
Closest in time.
Ma, Z.Z. andWu, Y.Y. (2015). Supplement to “Computational barriers in minimax submatrix detection.” DOI: \doiurl
2015
Closest in time.