Fetching the paper…
Reading the bibliography…
We study polynomial time algorithms for estimating the mean of a heavy-tailed multivariate random vector.
John W Tukey, A survey of sampling from contaminated distributions , Contributions to probability and statistics (1960), 448–485
1960
Earlier work this paper cites.
Peter J Huber, Robust estimation of a location parameter , The Annals of Mathematical Statistics 35
1964
Earlier work this paper cites.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin, Problem complexity and method efficiency in optimization. , SIAM Review 27
1983
Earlier work this paper cites.
Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani, Random generation of combinatorial structures from a uniform distribution , Theoretical Computer Science 43
1986
Earlier work this paper cites.
Naum Zuselevich Shor, An approach to obtaining global extremums in polynomial mathematical programming problems , Cybernetics 23
1987
Earlier work this paper cites.
Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , J. ACM 42
1995
Earlier work this paper cites.
Yurii Nesterov, Semidefinite relaxation and nonconvex quadratic optimization , Optimization Methods and Software 9
1998
Earlier work this paper cites.
Lieven Vandenberghe, Stephen Boyd, and Shao-Po Wu, Determinant maximization with linear matrix inequality constraints , SIAM journal on matrix analysis and applications 19
1998
Earlier work this paper cites.
Noga Alon, Yossi Matias, and Mario Szegedy, The space complexity of approximating the frequency moments , Journal of Computer and System Sciences 58
1999
Earlier work this paper cites.
Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos, On power-law relationships of the internet topology , ACM SIGCOMM Computer Communication Review, vol. 29, ACM, 1999, pp. 251–262
1999
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, California Institute of Technology, 2000
2000
Earlier work this paper cites.
Erhard Rahm and Hong Hai Do, Data cleaning: Problems and current approaches , IEEE Data Eng. Bull. 23
2000
Earlier work this paper cites.
Jean B Lasserre, Global optimization with polynomials and the problem of moments , SIAM Journal on Optimization 11
2001
Earlier work this paper cites.
Stephen Boyd and Lieven Vandenberghe, Convex optimization , Cambridge university press, 2004
2004
Earlier work this paper cites.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations , Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, ACM, 2005, pp. 177–187
2005
Earlier work this paper cites.
Noga Alon and Assaf Naor, Approximating the cut-norm via Grothendieck’s inequality , SIAM J. Comput. 35
2006
Earlier work this paper cites.
Thorsten Bernholt, Robust estimators are hard to compute , Tech. report, Technical Report/Universitat Dortmund, 2006
2006
Earlier work this paper cites.
Alexandre d’Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet, A direct formulation for sparse PCA using semidefinite programming , SIAM Review 49
2007
Earlier work this paper cites.
Arash A. Amini and Martin J. Wainwright, High-dimensional analysis of semidefinite relaxations for sparse principal components , ISIT, IEEE, 2008, pp. 2454–2458
2008
Cited alongside, same era.
Emmanuel J. Candès and Benjamin Recht, Exact matrix completion via convex optimization , Foundations of Computational Mathematics 9
2009
Cited alongside, same era.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, Inference and phase transitions in the detection of modules in sparse networks , Physical Review Letters 107
2011
Cited alongside, same era.
2011
Cited alongside, same era.
David P. Williamson and David B. Shmoys, The design of approximation algorithms , Cambridge University Press, 2011
Andrea Montanari and Subhabrata Sen, Semidefinite programs on sparse random graphs and their application to community detection , Proceedings of the forty-eighth annual ACM Symposium on Theory of Computing (STOC), ACM, 2016, pp. 814–827
2016
Later among the works it cites.
Tengyu Ma, Jonathan Shi, and David Steurer, Polynomial-time tensor decompositions with sum-of-squares , FOCS, IEEE Computer Society, 2016, pp. 438–446
2016
Later among the works it cites.
Jess Banks, Robert Kleinberg, and Cristopher Moore, The Lovasz theta function for random regular graphs and community detection in the hard regime , 21st International Conference on Randomization and Computation (RANDOM) (2017)
2017
Later among the works it cites.
Boaz Barak and David Steurer, The sos algorithm over general domains , Lecture notes: Proofs, Beliefs and Algorithms through the Lens of Sum of Squares (2017), https://www.sumofsquares.org/public/lec-definitions-general.html
2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2011
Cited alongside, same era.
Olivier Catoni, Challenging the empirical mean and empirical variance: a deviation study , Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, vol. 48, Institut Henri Poincaré, 2012, pp. 1148–1185
2012
Cited alongside, same era.
Quentin Berthet and Philippe Rigollet, Complexity theoretic lower bounds for sparse principal component detection , COLT, JMLR Workshop and Conference Proceedings, vol. 30, JMLR.org, 2013, pp. 1046–1066
2013
Cited alongside, same era.
Robert Krauthgamer, Boaz Nadler, and Dan Vilenchik, Do semidefinite relaxations solve sparse pca up to the information limit? , The Annals of Statistics 43
2015
Cited alongside, same era.
Stanislav Minsker, Geometric median and robust estimation in banach spaces , Bernoulli 21
2015
Cited alongside, same era.
Tengyu Ma and Avi Wigderson, Sum-of-squares lower bounds for sparse PCA , NIPS, 2015, pp. 1612–1620
2015
Cited alongside, same era.
Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall, Exact recovery in the stochastic block model , IEEE Transactions on Information Theory 62
2016
Cited alongside, same era.
Boaz Barak and Ankur Moitra, Noisy tensor completion via the sum-of-squares hierarchy , COLT, JMLR Workshop and Conference Proceedings, vol. 49, JMLR.org, 2016, pp. 417–445
2016
Cited alongside, same era.
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, The power of sum-of-squares for detecting hidden structures , Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, IEEE, 2017, pp. 720–731
2017
Later among the works it cites.
Samuel B Hopkins and David Steurer, Efficient bayesian estimation from few samples: community detection and related problems , Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, IEEE, 2017, pp. 379–390
2017
Later among the works it cites.
Aaron Potechin and David Steurer, Exact tensor completion with sum-of-squares , Proceedings of Machine Learning Research vol 65
2017
Later among the works it cites.
2017
Later among the works it cites.
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani, Inapproximability of matrix p → \rightarrow q norms , Electronic Colloquium on Computational Complexity (ECCC), vol. 25, 2018, p. 37
2018
Closest in time.
Samuel B Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 1021–1034
2018
Closest in time.
2018
Closest in time.
Pravesh K Kothari, Jacob Steinhardt, and David Steurer, Robust moment estimation and improved clustering via sum of squares , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 1035–1046
2018
Closest in time.
Gábor Lugosi and Shahar Mendelson, Sub-gaussian estimators of the mean of a random vector , Annals of Statistics (2018)
2018
Closest in time.
2018
Closest in time.
Tengyao Wang and Richard J Samworth, High dimensional change point estimation via sparse projection , Journal of the Royal Statistical Society: Series B (Statistical Methodology) 80
2018
Closest in time.
2019
Closest in time.
Emmanuel J. Candès and Terence Tao, The power of convex relaxation: near-optimal matrix completion , IEEE Trans. Information Theory 56
2080
Closest in time.