{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:22:46Z","timestamp":1775024566483,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,5,31]],"date-time":"2014-05-31T00:00:00Z","timestamp":1401494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,5,31]]},"DOI":"10.1145\/2591796.2591886","type":"proceedings-article","created":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T12:01:58Z","timestamp":1443700918000},"page":"31-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Rounding sum-of-squares relaxations"],"prefix":"10.1145","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[{"name":"Microsoft Research, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan A.","family":"Kelner","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Learning sparsely used overcomplete dictionaries via alternating minimization. arXiv preprint 1310.7991","author":"Agarwal A.","year":"2013","unstructured":"A. Agarwal , A. Anandkumar , P. Jain , P. Netrapalli , and R. Tandon . Learning sparsely used overcomplete dictionaries via alternating minimization. arXiv preprint 1310.7991 , 2013 . http:\/\/arxiv.org\/abs\/1310.7991. A. Agarwal, A. Anandkumar, P. Jain, P. Netrapalli, and R. Tandon. Learning sparsely used overcomplete dictionaries via alternating minimization. arXiv preprint 1310.7991, 2013. http:\/\/arxiv.org\/abs\/1310.7991."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214055"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"e_1_3_2_2_6_1","volume-title":"New algorithms for learning incoherent and overcomplete dictionaries. arXiv preprint 1308.6723","author":"Arora S.","year":"2013","unstructured":"S. Arora , R. Ge , and A. Moitra . New algorithms for learning incoherent and overcomplete dictionaries. arXiv preprint 1308.6723 , 2013 . http:\/\/arxiv.org\/abs\/1308.6273. S. Arora, R. Ge, and A. Moitra. New algorithms for learning incoherent and overcomplete dictionaries. arXiv preprint 1308.6723, 2013. http:\/\/arxiv.org\/abs\/1308.6273."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.83"},{"key":"e_1_3_2_2_10_1","volume-title":"Iterative rounding for sum-of-squares relaxations. Preliminary version of the current work, unpublished","author":"Barak B.","year":"2012","unstructured":"B. Barak , J. Kelner , and D. Steurer . Iterative rounding for sum-of-squares relaxations. Preliminary version of the current work, unpublished , 2012 . B. Barak, J. Kelner, and D. Steurer. Iterative rounding for sum-of-squares relaxations. Preliminary version of the current work, unpublished, 2012."},{"key":"e_1_3_2_2_11_1","volume-title":"Rounding sum-of-squares relaxations. arXiv preprint arXiv:1312.6652","author":"Barak B.","year":"2013","unstructured":"B. Barak , J. Kelner , and D. Steurer . Rounding sum-of-squares relaxations. arXiv preprint arXiv:1312.6652 , 2013 . Full version of the current work. B. Barak, J. Kelner, and D. Steurer. Rounding sum-of-squares relaxations. arXiv preprint arXiv:1312.6652, 2013. Full version of the current work."},{"key":"e_1_3_2_2_12_1","volume-title":"Dictionary learning via the sum-of-squares method. Manuscript in preparation","author":"Barak B.","year":"2014","unstructured":"B. Barak , J. Kelner , and D. Steurer . Dictionary learning via the sum-of-squares method. Manuscript in preparation , 2014 . B. Barak, J. Kelner, and D. Steurer. Dictionary learning via the sum-of-squares method. Manuscript in preparation, 2014."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a012"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095150"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993683"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488718"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_2_20_1","volume-title":"Convex relaxations and integrality gaps","author":"Chlamtac E.","year":"2010","unstructured":"E. Chlamtac and M. Tulsiani . Convex relaxations and integrality gaps , 2010 . Chapter in Handbook on Semidefinite, Cone and Polynomial Optimization . E. Chlamtac and M. Tulsiani. Convex relaxations and integrality gaps, 2010. Chapter in Handbook on Semidefinite, Cone and Polynomial Optimization."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283390"},{"key":"e_1_3_2_2_22_1","volume-title":"Oct.","author":"Demanet L.","year":"2013","unstructured":"L. Demanet and P. Hand . Recovering the Sparsest Element in a Subspace , Oct. 2013 . Arxiv preprint 1310.1654. L. Demanet and P. Hand. Recovering the Sparsest Element in a Subspace, Oct. 2013. Arxiv preprint 1310.1654."},{"key":"e_1_3_2_2_23_1","volume-title":"Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv preprint arXiv:1210.5048","author":"Doherty A. C.","year":"2012","unstructured":"A. C. Doherty and S. Wehner . Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv preprint arXiv:1210.5048 , 2012 . A. C. Doherty and S. Wehner. Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv preprint arXiv:1210.5048, 2012."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886538"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8192-0"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432625"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634193"},{"key":"e_1_3_2_2_33_1","first-page":"25","volume-title":"IEEE Conference on Computational Complexity","author":"Khot S.","year":"2002","unstructured":"S. Khot . On the power of unique 2-prover 1-round games . In IEEE Conference on Computational Complexity , page 25 , 2002 . S. Khot. On the power of unique 2-prover 1-round games. In IEEE Conference on Computational Complexity, page 25, 2002."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_3_2_2_35_1","volume-title":"Hidden cliques and the certification of the restricted isometry property. CoRR, abs\/1211.0665","author":"Koiran P.","year":"2012","unstructured":"P. Koiran and A. Zouzias . Hidden cliques and the certification of the restricted isometry property. CoRR, abs\/1211.0665 , 2012 . P. Koiran and A. Zouzias. Hidden cliques and the certification of the restricted isometry property. CoRR, abs\/1211.0665, 2012."},{"key":"e_1_3_2_2_36_1","volume-title":"Anneaux pr\u00e9ordonn\u00e9s. Journal d'analyse math\u00e9matique, 12(1):307--326","author":"Krivine J.-L.","year":"1964","unstructured":"J.-L. Krivine . Anneaux pr\u00e9ordonn\u00e9s. Journal d'analyse math\u00e9matique, 12(1):307--326 , 1964 . J.-L. Krivine. Anneaux pr\u00e9ordonn\u00e9s. Journal d'analyse math\u00e9matique, 12(1):307--326, 1964."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_3_2_2_40_1","volume-title":"High performance optimization, 13:405--440","author":"Nesterov Y.","year":"2000","unstructured":"Y. Nesterov . Squared functional systems and optimization problems. High performance optimization, 13:405--440 , 2000 . Y. Nesterov. Squared functional systems and optimization problems. High performance optimization, 13:405--440, 2000."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627928"},{"key":"e_1_3_2_2_43_1","volume-title":"Complexity of constraint satisfaction problems: Exact and approximate","author":"Raghavendra P.","year":"2010","unstructured":"P. Raghavendra . Complexity of constraint satisfaction problems: Exact and approximate , 2010 . Talk at the Institute for Advanced Study , video available on http:\/\/video.ias.edu\/csdm\/complexityconstraint. P. Raghavendra. Complexity of constraint satisfaction problems: Exact and approximate, 2010. Talk at the Institute for Advanced Study, video available on http:\/\/video.ias.edu\/csdm\/complexityconstraint."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806776"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"issue":"5","key":"e_1_3_2_2_49_1","first-page":"695","article-title":"An approach to obtaining global extremums in polynomial mathematical programming problems","volume":"23","author":"Shor N.","year":"1987","unstructured":"N. Shor . An approach to obtaining global extremums in polynomial mathematical programming problems . Cybernetics and Systems Analysis , 23 ( 5 ): 695 -- 700 , 1987 . N. Shor. An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics and Systems Analysis, 23(5):695--700, 1987.","journal-title":"Cybernetics and Systems Analysis"},{"key":"e_1_3_2_2_50_1","volume-title":"Exact recovery of sparsely-used dictionaries. Journal of Machine Learning Research - Proceedings Track, 23:37.1--37.18","author":"Spielman D. A.","year":"2012","unstructured":"D. A. Spielman , H. Wang , and J. Wright . Exact recovery of sparsely-used dictionaries. Journal of Machine Learning Research - Proceedings Track, 23:37.1--37.18 , 2012 . D. A. Spielman, H. Wang, and J. Wright. Exact recovery of sparsely-used dictionaries. Journal of Machine Learning Research - Proceedings Track, 23:37.1--37.18, 2012."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01362149"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976601300014385"}],"event":{"name":"STOC '14: Symposium on Theory of Computing","location":"New York New York","acronym":"STOC '14","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591886","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591796.2591886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:55:45Z","timestamp":1750229745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":52,"alternative-id":["10.1145\/2591796.2591886","10.1145\/2591796"],"URL":"https:\/\/doi.org\/10.1145\/2591796.2591886","relation":{},"subject":[],"published":{"date-parts":[[2014,5,31]]},"assertion":[{"value":"2014-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}