{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T14:26:26Z","timestamp":1775571986550,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1565264, CNS 1618026, Career Award"],"award-info":[{"award-number":["CCF 1565264, CNS 1618026, Career Award"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055488","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"975-988","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Quantum entanglement, sum of squares, and the log rank conjecture"],"prefix":"10.1145","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Princeton University, USA \/ IAS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University, USA \/ IAS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993683"},{"key":"e_1_3_2_2_2_1","volume-title":"The mathematics of entanglement, arXiv preprint arXiv:1604.01790","author":"Brandao Fernando GSL","year":"2016","unstructured":"{BCHW16} Fernando GSL Brandao , Matthias Christandl , Aram W Harrow , and Michael Walter , The mathematics of entanglement, arXiv preprint arXiv:1604.01790 ( 2016 ). {BCHW16} Fernando GSL Brandao, Matthias Christandl, Aram W Harrow, and Michael Walter, The mathematics of entanglement, arXiv preprint arXiv:1604.01790 (2016)."},{"key":"e_1_3_2_2_3_1","volume-title":"Estimating operator norms using covering nets, CoRR abs\/1509.05065","author":"Fernando G. S.","year":"2015","unstructured":"{BH15} Fernando G. S. L. Brand\u00e3o and Aram Wettroth Harrow , Estimating operator norms using covering nets, CoRR abs\/1509.05065 ( 2015 ). {BH15} Fernando G. S. L. Brand\u00e3o and Aram Wettroth Harrow, Estimating operator norms using covering nets, CoRR abs\/1509.05065 (2015)."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_2_5_1","volume-title":"beliefs, and algorithms through the lens of sum-of-squares","author":"Barak Boaz","year":"2016","unstructured":"{BKS16} Boaz Barak , Pravesh Kothari , and David Steurer , Proofs , beliefs, and algorithms through the lens of sum-of-squares , 2016 , Lecture notes in preparation, available on http:\/\/sumofsquares.org. {BKS16} Boaz Barak, Pravesh Kothari, and David Steurer, Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016, Lecture notes in preparation, available on http:\/\/sumofsquares.org."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICQNM.2009.21"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.69.022308"},{"key":"e_1_3_2_2_8_1","volume-title":"Convergence of SDP hierarchies for polynomial optimization on the hypersphere, CoRR abs\/1210.5048","author":"Andrew","year":"2012","unstructured":"{DW12} Andrew C. Doherty and Stephanie Wehner , Convergence of SDP hierarchies for polynomial optimization on the hypersphere, CoRR abs\/1210.5048 ( 2012 ). {DW12} Andrew C. Doherty and Stephanie Wehner, Convergence of SDP hierarchies for polynomial optimization on the hypersphere, CoRR abs\/1210.5048 (2012)."},{"key":"e_1_3_2_2_9_1","first-page":"3","article-title":"Strong np-hardness of the quantum separability problem, Quantum Information &","volume":"10","author":"Gharibian Sevag","year":"2010","unstructured":"{Gha10} Sevag Gharibian , Strong np-hardness of the quantum separability problem, Quantum Information & Computation 10 ( 2010 ), no. 3 , 343\u2013360. {Gha10} Sevag Gharibian, Strong np-hardness of the quantum separability problem, Quantum Information & Computation 10 (2010), no. 3, 343\u2013360.","journal-title":"Computation"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780545"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(96)00706-2"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432625"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.62.052310"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591799"},{"key":"e_1_3_2_2_15_1","first-page":"90","volume-title":"IEEE Computer Society","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1988","unstructured":"{LS88} L\u00e1szl\u00f3 Lov\u00e1sz and Michael E . Saks, Lattices, m\u00f6bius functions and communication complexity, FOCS , IEEE Computer Society , 1988 , pp. 81\u2013 90 . {LS88} L\u00e1szl\u00f3 Lov\u00e1sz and Michael E. Saks, Lattices, m\u00f6bius functions and communication complexity, FOCS, IEEE Computer Society, 1988, pp. 81\u201390."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365711"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/253\/03936"},{"key":"e_1_3_2_2_18_1","volume-title":"Pravesh K. Kothari, and David Steurer {Sta82} A. J. Stam, Limit theorems for uniform distributions on spheres in highdimensional Euclidean spaces, J. Appl. Probab. 19","author":"June","year":"1982","unstructured":"STOC\u201917, June 2017, Montreal , Canada Boaz Barak , Pravesh K. Kothari, and David Steurer {Sta82} A. J. Stam, Limit theorems for uniform distributions on spheres in highdimensional Euclidean spaces, J. Appl. Probab. 19 ( 1982 ), no. 1, 221\u2013228. MR 644435 {Ved08} Vlatko Vedral, Quantifying entanglement in macroscopic systems, Nature 453 (2008), no. 7198, 1004\u20131007. STOC\u201917, June 2017, Montreal, Canada Boaz Barak, Pravesh K. Kothari, and David Steurer {Sta82} A. J. Stam, Limit theorems for uniform distributions on spheres in highdimensional Euclidean spaces, J. Appl. Probab. 19 (1982), no. 1, 221\u2013228. MR 644435 {Ved08} Vlatko Vedral, Quantifying entanglement in macroscopic systems, Nature 453 (2008), no. 7198, 1004\u20131007."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.147902"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055488","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055488","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":19,"alternative-id":["10.1145\/3055399.3055488","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055488","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}