{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T11:05:29Z","timestamp":1776337529065,"version":"3.51.2"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006445","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006445","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897529","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"178-191","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors"],"prefix":"10.1145","author":[{"given":"Samuel B.","family":"Hopkins","sequence":"first","affiliation":[{"name":"Cornell University, USA"}]},{"given":"Tselil","family":"Schramm","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"Jonathan","family":"Shi","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9909-1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670323"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2697055"},{"key":"e_1_3_2_1_4_1","volume-title":"Analyzing tensor power method dynamics: Applications to learning overcomplete latent variable models. CoRR, abs\/1411.1488","author":"Anandkumar A.","year":"2014","unstructured":"A. Anandkumar , R. Ge , and M. Janzamin . Analyzing tensor power method dynamics: Applications to learning overcomplete latent variable models. CoRR, abs\/1411.1488 , 2014 . A. Anandkumar, R. Ge, and M. Janzamin. Analyzing tensor power method dynamics: Applications to learning overcomplete latent variable models. CoRR, abs\/1411.1488, 2014."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Anandkumar A.","year":"2015","unstructured":"A. Anandkumar , R. Ge , and M. Janzamin . Learning overcomplete latent variable models through tensor methods . In Proceedings of The 28th Conference on Learning Theory, COLT 2015 , Paris, France, July 3-6, pages 36\u2013112 , 2015 . A. Anandkumar, R. Ge, and M. Janzamin. Learning overcomplete latent variable models through tensor methods. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, pages 36\u2013112, 2015."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_9_1","volume-title":"Tensor prediction, rademacher complexity and random 3-xor. CoRR, abs\/1501.06521","author":"Barak B.","year":"2015","unstructured":"B. Barak and A. Moitra . Tensor prediction, rademacher complexity and random 3-xor. CoRR, abs\/1501.06521 , 2015 . B. Barak and A. Moitra. Tensor prediction, rademacher complexity and random 3-xor. CoRR, abs\/1501.06521, 2015."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_11_1","volume-title":"Sum-of-squares proofs and the quest toward optimal algorithms. CoRR, abs\/1404.5236","author":"Barak B.","year":"2014","unstructured":"B. Barak and D. Steurer . Sum-of-squares proofs and the quest toward optimal algorithms. CoRR, abs\/1404.5236 , 2014 . B. Barak and D. Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. CoRR, abs\/1404.5236, 2014."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5564(96)00075-2"},{"key":"e_1_3_2_1_14_1","volume-title":"NIPS 2004","author":"Aspremont A.","year":"2004","unstructured":"A. d\u2019 Aspremont , L. E. Ghaoui , M. I. Jordan , and G. R. G. Lanckriet . A direct formulation for sparse PCA using semidefinite programming. In Advances in Neural Information Processing Systems 17 {Neural Information Processing Systems , NIPS 2004 , December 13-18, Vancouver, British Columbia, Canada}, pages 41\u201348 , 2004 . A. d\u2019Aspremont, L. E. Ghaoui, M. I. Jordan, and G. R. G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. In Advances in Neural Information Processing Systems 17 {Neural Information Processing Systems, NIPS 2004, December 13-18, Vancouver, British Columbia, Canada}, pages 41\u201348, 2004."},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"de la Vega W. F.","year":"2007","unstructured":"W. F. de la Vega and C. Kenyon-Mathieu . Linear programming relaxations of maxcut . In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 , New Orleans, Louisiana, USA, January 7-9, pages 53\u201361 , 2007 . W. F. de la Vega and C. Kenyon-Mathieu. Linear programming relaxations of maxcut. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, pages 53\u201361, 2007."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau007"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_1_19_1","first-page":"849","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM","author":"Ge R.","year":"2015","unstructured":"R. Ge and T. Ma . Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015 , August 24-26, Princeton, NJ, USA , pages 829\u2013 849 , 2015. R. Ge and T. Ma. Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, August 24-26, Princeton, NJ, USA, pages 829\u2013849, 2015."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591875"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.58"},{"key":"e_1_3_2_1_22_1","first-page":"1","article-title":"\u201cexplanatory","volume":"16","author":"Harshman R. A.","year":"1970","unstructured":"R. A. Harshman . Foundations of the PARAFAC procedure: Models and conditions for an \u201cexplanatory \u201d multi-modal factor analysis. UCLA Working Papers in Phonetics , 16 : 1 \u2013 84 , 1970 . R. A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an \u201cexplanatory\u201d multi-modal factor analysis. UCLA Working Papers in Phonetics, 16:1\u201384, 1970.","journal-title":"UCLA Working Papers in Phonetics"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512329"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Hopkins S. B.","year":"2015","unstructured":"S. B. Hopkins , J. Shi , and D. Steurer . Tensor principal component analysis via sum-of-square proofs . In Proceedings of The 28th Conference on Learning Theory, COLT 2015 , Paris, France, July 3-6, pages 956\u20131006 , 2015 . S. B. Hopkins, J. Shi, and D. Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, pages 956\u20131006, 2015."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.893943"},{"key":"e_1_3_2_1_29_1","volume-title":"A lasserre-based (1 + \u03b5)-approximation for P m |","author":"Levey E.","year":"2015","unstructured":"E. Levey and T. Rothvoss . A lasserre-based (1 + \u03b5)-approximation for P m | p j = 1, prec | C max. CoRR , abs\/1509.07808, 2015 . E. Levey and T. Rothvoss. A lasserre-based (1 + \u03b5)-approximation for P m | p j = 1, prec | C max. CoRR, abs\/1509.07808, 2015."},{"key":"e_1_3_2_1_30_1","volume-title":"Sum-of-squares lower bounds for sparse PCA. CoRR, abs\/1507.06370","author":"Ma T.","year":"2015","unstructured":"T. Ma and A. Wigderson . Sum-of-squares lower bounds for sparse PCA. CoRR, abs\/1507.06370 , 2015 . T. Ma and A. Wigderson. Sum-of-squares lower bounds for sparse PCA. CoRR, abs\/1507.06370, 2015."},{"key":"e_1_3_2_1_31_1","volume-title":"Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. CoRR, abs\/1307.7615","author":"Meka R.","year":"2013","unstructured":"R. Meka and A. Wigderson . Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. CoRR, abs\/1307.7615 , 2013 . R. Meka and A. Wigderson. Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique. CoRR, abs\/1307.7615, 2013."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051606000000024"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9031-0"},{"key":"e_1_3_2_1_35_1","volume-title":"Citeseer","author":"Parrilo P. A.","year":"2000","unstructured":"P. A. Parrilo . Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis , Citeseer , 2000 . P. A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, Citeseer, 2000."},{"key":"e_1_3_2_1_36_1","volume-title":"Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Qu Q.","year":"2014","unstructured":"Q. Qu , J. Sun , and J. Wright . Finding a sparse vector in a subspace: Linear sparsity using alternating directions . In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 , December 8-13 2014 , Montreal, Quebec, Canada, pages 3401\u20133409 , 2014. Q. Qu, J. Sun, and J. Wright. Finding a sparse vector in a subspace: Linear sparsity using alternating directions. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 3401\u20133409, 2014."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095149"},{"key":"e_1_3_2_1_38_1","volume-title":"Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Richard E.","year":"2014","unstructured":"E. Richard and A. Montanari . A statistical model for tensor PCA . In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 , December 8-13 2014 , Montreal, Quebec, Canada, pages 2897\u20132905 , 2014. E. Richard and A. Montanari. A statistical model for tensor PCA. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 2897\u20132905, 2014."},{"key":"e_1_3_2_1_39_1","first-page":"136","article-title":"An approach to obtaining global extrema in polynomial problems of mathematical programming","volume":"102","author":"Shor N. Z.","year":"1987","unstructured":"N. Z. Shor . An approach to obtaining global extrema in polynomial problems of mathematical programming . Kibernetika (Kiev), (5) : 102\u2013106 , 136 , 1987 . N. Z. Shor. An approach to obtaining global extrema in polynomial problems of mathematical programming. Kibernetika (Kiev), (5):102\u2013106, 136, 1987.","journal-title":"Kibernetika (Kiev), (5)"},{"key":"e_1_3_2_1_40_1","volume-title":"COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27","author":"Spielman D. A.","year":"2012","unstructured":"D. A. Spielman , H. Wang , and J. Wright . Exact recovery of sparsely-used dictionaries . In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27 , Edinburgh, Scotland, pages 37.1\u201337.18 , 2012 . D. A. Spielman, H. Wang, and J. Wright. Exact recovery of sparsely-used dictionaries. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, Edinburgh, Scotland, pages 37.1\u201337.18, 2012."},{"key":"e_1_3_2_1_41_1","unstructured":"Linear Algebra and Matrix Concentration  Linear Algebra and Matrix Concentration"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897529","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897529","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:02Z","timestamp":1750221542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897529"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":41,"alternative-id":["10.1145\/2897518.2897529","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897529","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}