{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T05:59:52Z","timestamp":1776146392363,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214006","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"307-326","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":77,"title":["Hypercontractivity, sum-of-squares proofs, and their applications"],"prefix":"10.1145","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[{"name":"Microsoft Research New England, Cambridge, MA, USA"}]},{"given":"Fernando G.S.L.","family":"Brandao","sequence":"additional","affiliation":[{"name":"Universidade Federal de Minas Gerais, Belo Horizonte, Brazil"}]},{"given":"Aram W.","family":"Harrow","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]},{"given":"Jonathan","family":"Kelner","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Microsoft Research New England, Cambridge, MA, USA"}]},{"given":"Yuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Carnegie Melon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.26"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993683"},{"key":"e_1_3_2_2_4_1","volume-title":"Making the long code shorter, with applications to the unique games conjecture","author":"Barak Boaz","year":"2011","unstructured":"Boaz Barak , Parikshit Gopalan , Johan H\u00e5stad , Raghu Meka , Prasad Raghavendra , and David Steurer , Making the long code shorter, with applications to the unique games conjecture , 2011 , Manuscript . Boaz Barak, Parikshit Gopalan, Johan H\u00e5stad, Raghu Meka, Prasad Raghavendra, and David Steurer, Making the long code shorter, with applications to the unique games conjecture, 2011, Manuscript."},{"key":"e_1_3_2_2_5_1","volume-title":"Manuscript. Available as eprint \\hrefhttp:\/\/arxiv.org\/abs\/1101.2913arXiv:1101.2913v1","author":"Biswal Punyashloka","year":"2011","unstructured":"Punyashloka Biswal , Hypercontractivity and its applications , Manuscript. Available as eprint \\hrefhttp:\/\/arxiv.org\/abs\/1101.2913arXiv:1101.2913v1 , 2011 . Punyashloka Biswal, Hypercontractivity and its applications, Manuscript. Available as eprint \\hrefhttp:\/\/arxiv.org\/abs\/1101.2913arXiv:1101.2913v1, 2011."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3364793"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.769"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133076"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1494475"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-007-0189-3"},{"key":"e_1_3_2_2_12_1","first-page":"4","article-title":"Remarks on symmetries of trilinear forms","volume":"94","author":"Cobos Fernando","year":"2000","unstructured":"Fernando Cobos , Thomas K\u00fchn , and Jaak Peetre , Remarks on symmetries of trilinear forms , Rev. R. Acad. Cienc. Exact. Fis.Nat. (Esp) 94 ( 2000 ), no. 4 , 441--449. Fernando Cobos, Thomas K\u00fchn, and Jaak Peetre, Remarks on symmetries of trilinear forms, Rev. R. Acad. Cienc. Exact. Fis.Nat. (Esp) 94 (2000), no. 4, 441--449.","journal-title":"Rev. R. Acad. Cienc. Exact. Fis.Nat. (Esp)"},{"key":"e_1_3_2_2_13_1","volume-title":"Convex relaxations and integrality gaps","author":"Chlamtac Eden","year":"2010","unstructured":"Eden Chlamtac and Madhur Tulsiani , Convex relaxations and integrality gaps , 2010 , Chapter in Handbook on Semidefinite, Cone and Polynomial Optimization . Eden Chlamtac and Madhur Tulsiani, Convex relaxations and integrality gaps, 2010, Chapter in Handbook on Semidefinite, Cone and Polynomial Optimization."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814147"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060701"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.69.022308"},{"key":"e_1_3_2_2_17_1","unstructured":"Francois Le Gall Shota Nakagawa and Harumichi Nishimura On qma protocols with two short quantum proofs arXiv:1108.4306.  Francois Le Gall Shota Nakagawa and Harumichi Nishimura On qma protocols with two short quantum proofs arXiv:1108.4306."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/2373688"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780545"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(96)00706-2"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.66"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796440"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.49"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2018158.2018182"},{"key":"e_1_3_2_2_27_1","first-page":"64","volume-title":"SODA","author":"Kindler Guy","year":"2008","unstructured":"Guy Kindler , Assaf Naor , and Gideon Schechtman , The UGC hardness threshold of the $\\ell_p$ Grothendieck problem , SODA , 2008 , pp. 64 -- 73 . Guy Kindler, Assaf Naor, and Gideon Schechtman, The UGC hardness threshold of the $\\ell_p$ Grothendieck problem, SODA, 2008, pp. 64--73."},{"key":"e_1_3_2_2_28_1","first-page":"298","article-title":"Approximate lasserre integrality gap for unique games","author":"Khot Subhash","year":"2010","unstructured":"Subhash Khot , Preyas Popat , and Rishi Saket , Approximate lasserre integrality gap for unique games , APPROX-RANDOM , 2010 , pp. 298 -- 311 . Subhash Khot, Preyas Popat, and Rishi Saket, Approximate lasserre integrality gap for unique games, APPROX-RANDOM, 2010, pp. 298--311.","journal-title":"APPROX-RANDOM"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.37"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_2_33_1","volume-title":"Emerging applications of algebraic geometry 149","author":"Laurent M.","year":"2009","unstructured":"M. Laurent , Sums of squares, moment matrices and optimization over polynomials , Emerging applications of algebraic geometry 149 ( 2009 ), 157--270. M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry 149 (2009), 157--270."},{"key":"e_1_3_2_2_34_1","unstructured":"Yi-Kai. Liu The complexity of the consistency and N-representability problems for quantum states Ph.D. thesis Univ. of California San Diego 2007 arXiv:0712.3041.   Yi-Kai. Liu The complexity of the consistency and N-representability problems for quantum states Ph.D. thesis Univ. of California San Diego 2007 arXiv:0712.3041."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_3_2_2_37_1","volume-title":"High performance optimization 13","author":"Nesterov Y.","year":"2000","unstructured":"Y. Nesterov , Squared functional systems and optimization problems , High performance optimization 13 ( 2000 ). Y. Nesterov, Squared functional systems and optimization problems, High performance optimization 13 (2000)."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.052306"},{"key":"e_1_3_2_2_39_1","volume-title":"Lecture Notes. Available online at \\hrefhttp:\/\/www.cs.cmu.edu\/ odonnell\/boolean-analysis\/http:\/\/www.cs.cmu.e%du\/\\ odonnell\/boolean-analysis\/","author":"O'Donnell Ryan","year":"2007","unstructured":"Ryan O'Donnell , Analysis of boolean functions , Lecture Notes. Available online at \\hrefhttp:\/\/www.cs.cmu.edu\/ odonnell\/boolean-analysis\/http:\/\/www.cs.cmu.e%du\/\\ odonnell\/boolean-analysis\/ , 2007 . Ryan O'Donnell, Analysis of boolean functions, Lecture Notes. Available online at \\hrefhttp:\/\/www.cs.cmu.edu\/ odonnell\/boolean-analysis\/http:\/\/www.cs.cmu.e%du\/\\ odonnell\/boolean-analysis\/, 2007."},{"key":"e_1_3_2_2_40_1","volume-title":"Tech. report","author":"Parrilo Pablo A.","year":"2000","unstructured":"Pablo A. Parrilo , Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Tech. report , 2000 . Pablo A. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Tech. report, 2000."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.73"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806776"},{"key":"e_1_3_2_2_45_1","volume-title":"Manuscript. Available as eprint \\hrefhttp:\/\/arxiv.org\/abs\/1011.2586arXiv:1011.2586v1","author":"Raghavendra Prasad","year":"2010","unstructured":"Prasad Raghavendra , David Steurer , and Madhur Tulsiani , Reductions between expansion problems , Manuscript. Available as eprint \\hrefhttp:\/\/arxiv.org\/abs\/1011.2586arXiv:1011.2586v1 , 2010 . Prasad Raghavendra, David Steurer, and Madhur Tulsiani, Reductions between expansion problems, Manuscript. Available as eprint \\hrefhttp:\/\/arxiv.org\/abs\/1011.2586arXiv:1011.2586v1, 2010."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-3903-4","volume-title":"Introduction to tensor products of banach spaces","author":"Ryan Raymond A.","year":"2002","unstructured":"Raymond A. Ryan , Introduction to tensor products of banach spaces , Springer monographs in mathematics, Springer , 2002 . Raymond A. Ryan, Introduction to tensor products of banach spaces, Springer monographs in mathematics, Springer, 2002."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_2_48_1","volume-title":"Lectures on probability theory and statistics 1665","author":"Saloff-Coste Laurent","year":"1997","unstructured":"Laurent Saloff-Coste , Lectures on finite markov chains , Lectures on probability theory and statistics 1665 ( 1997 ), 301--413. Laurent Saloff-Coste, Lectures on finite markov chains, Lectures on probability theory and statistics 1665 (1997), 301--413."},{"key":"e_1_3_2_2_49_1","first-page":"5","article-title":"An approach to obtaining global extremums in polynomial mathematical programming problems","volume":"23","author":"Shor NZ","year":"1987","unstructured":"NZ Shor , An approach to obtaining global extremums in polynomial mathematical programming problems , Cybernetics and Systems Analysis 23 ( 1987 ), no. 5 , 695--700. NZ Shor, An approach to obtaining global extremums in polynomial mathematical programming problems, Cybernetics and Systems Analysis 23 (1987), no. 5, 695--700.","journal-title":"Cybernetics and Systems Analysis"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0082586-0"},{"key":"e_1_3_2_2_51_1","volume-title":"Technion","author":"Steinberg Daureen","year":"2005","unstructured":"Daureen Steinberg , Computation of matrix norms with applications to robust optimization, Master's thesis , Technion , 2005 , Available on A. Nemirovski's website http:\/\/www2.isye.gatech.edu\/ nemirovs\/. Daureen Steinberg, Computation of matrix norms with applications to robust optimization, Master's thesis, Technion, 2005, Available on A. Nemirovski's website http:\/\/www2.isye.gatech.edu\/ nemirovs\/."},{"key":"e_1_3_2_2_52_1","volume-title":"Manuscript, available from the author's website.","author":"Steurer David","year":"2010","unstructured":"David Steurer , Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion , Manuscript, available from the author's website. , 2010 . David Steurer, Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion, Manuscript, available from the author's website., 2010."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_2_54_1","volume-title":"Unpublished NSF Workshop Report.","author":"van Loan Charles","unstructured":"Charles van Loan , Future directions in tensor-based computation and modeling, 2009 , Unpublished NSF Workshop Report. Charles van Loan, Future directions in tensor-based computation and modeling, 2009, Unpublished NSF Workshop Report."}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":54,"alternative-id":["10.1145\/2213977.2214006","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214006","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}