{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:09Z","timestamp":1750220529307,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF"},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1900460"],"award-info":[{"award-number":["CCF-1900460"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons collaboration on algorithms and geometry"],"award-info":[{"award-number":["Simons collaboration on algorithms and geometry"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Packard Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451128","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"870-881","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A framework for quadratic form maximization over convex sets through nonconvex relaxations"],"prefix":"10.1145","author":[{"given":"Vijay","family":"Bhattiprolu","sequence":"first","affiliation":[{"name":"Institute for Advanced Study at Princeton, USA \/ Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Naor","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Maximizing a quadratic form on the \\ell _1^n unit ball","author":"Alon Noga","year":"2006","unstructured":"Noga Alon. 2006. Maximizing a quadratic form on the \\ell _1^n unit ball. 2006."},{"key":"e_1_3_2_1_2_1","first-page":"3","article-title":"An asymptotic isoperimetric inequality","volume":"8","author":"Alon Noga","year":"1998","unstructured":"Noga Alon, Ravi Boppana, and Joel Spencer. 1998. An asymptotic isoperimetric inequality. Geometric & Functional Analysis GAFA, 8, 3, 1998. Pages 411\u2013436.","journal-title":"Geometric & Functional Analysis GAFA"},{"key":"e_1_3_2_1_3_1","volume-title":"Quadratic forms on graphs. Inventiones mathematicae, 163, 3","author":"Alon Noga","year":"2006","unstructured":"Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. 2006. Quadratic forms on graphs. Inventiones mathematicae, 163, 3, 2006. Pages 499\u2013522."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441629"},{"key":"e_1_3_2_1_5_1","volume-title":"Subspace embedding and linear regression with Orlicz norm. arXiv preprint arXiv:1806.06430","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong. 2018. Subspace embedding and linear regression with Orlicz norm. arXiv preprint arXiv:1806.06430, 2018."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055418"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.57"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_10_1","first-page":"441","volume-title":"Ser. A","author":"Bellare Mihir","year":"1995","unstructured":"Mihir Bellare and Phillip Rogaway. 1995. The complexity of approximating a nonlinear program. Math. Programming, 69, 3, Ser. A, 1995. Pages 429\u2013441. coden:MHPGA4 issn:0025-5610"},{"volume-title":"Interpolation spaces. An introduction","author":"Bergh J\u00f6ran","key":"e_1_3_2_1_11_1","unstructured":"J\u00f6ran Bergh and J\u00f6rgen L\u00f6fstr\u00f6m. 1976. Interpolation spaces. An introduction. Springer-Verlag, Berlin-New York."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"e_1_3_2_1_13_1","volume-title":"A framework for quadratic form maximization over convex sets through nonconvex relaxations. Soon to appear on arxiv","author":"Bhattiprolu Vijay","year":"2021","unstructured":"Vijay Bhattiprolu, Euiwoong Lee, and Assaf Naor. 2021. A framework for quadratic form maximization over convex sets through nonconvex relaxations. Soon to appear on arxiv, 2021."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Pages 716\u2013729","author":"Jaros\u0142","year":"2017","unstructured":"Jaros\u0142 aw B\u0142 asiok, Vladimir Braverman, Stephen R Chestnut, Robert Krauthgamer, and Lin F Yang. 2017. Streaming symmetric norms via measure concentration. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Pages 716\u2013729."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Mark Braverman Konstantin Makarychev Yury Makarychev and Assaf Naor. 2013. The Grothendieck constant is strictly smaller than Krivine's bound. In Forum of Mathematics Pi. 1","DOI":"10.1017\/fmp.2013.4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2756-x"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.72"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188930"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316322"},{"key":"e_1_3_2_1_20_1","volume-title":"Simpler and Better Algorithms for Minimum-Norm Load Balancing. arXiv preprint arXiv:1905.00044","author":"Chakrabarty Deeparnab","year":"2019","unstructured":"Deeparnab Chakrabarty and Chaitanya Swamy. 2019. Simpler and Better Algorithms for Minimum-Norm Load Balancing. arXiv preprint arXiv:1905.00044, 2019."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.39"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Pages 921\u2013939","author":"Clarkson Kenneth L","year":"2014","unstructured":"Kenneth L Clarkson and David P Woodruff. 2014. Sketching for M-estimators: A unified approach to robust regression. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Pages 921\u2013939."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-007-0052-9"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.011"},{"key":"e_1_3_2_1_25_1","first-page":"288","volume-title":"Proceedings of the 23rd International Conference on Machine Learning (ICML'06)","author":"Ding Chris","year":"2006","unstructured":"Chris Ding, Ding Zhou, Xiaofeng He, and Hongyuan Zha. 2006. R_1-PCA: Rotational invariant L_1-norm principal component analysis for robust subspace factorization. In Proceedings of the 23rd International Conference on Machine Learning (ICML'06). Pages 281\u2013\u2013288."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm-44-6-617-648"},{"volume-title":"STOC'92: Proceedings of the 24th Annual ACM Symposium on Theory of Computing. ACM. Pages 733\u2013744","author":"Feige U.","key":"e_1_3_2_1_27_1","unstructured":"U. Feige and L. Lov\u00e1sz. 1992. Two-prover one-round proof systems, their power and their problems. In STOC'92: Proceedings of the 24th Annual ACM Symposium on Theory of Computing. ACM. Pages 733\u2013744."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02774015"},{"key":"e_1_3_2_1_29_1","first-page":"829","volume-title":"Algorithms and Techniques","author":"Ge Rong","year":"2015","unstructured":"Rong Ge and Tengyu Ma. 2015. Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2015. Pages 829."},{"key":"e_1_3_2_1_30_1","first-page":"1953","article-title":"R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques","volume":"8","author":"Grothendieck Alexander","year":"1953","unstructured":"Alexander Grothendieck. 1953. R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. S\\~ao Paulo \\textbf 8, 1953.","journal-title":"Bol. Soc. Mat. S\\~ao Paulo \\textbf"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"M Grotschel L Lov\u00e1sz and A Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737729"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(85)90026-X"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.481"},{"key":"e_1_3_2_1_35_1","volume-title":"A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem","author":"Heilman Steven","year":"2016","unstructured":"Steven Heilman and Thomas Vidick. 2016. A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem. 2016. arxiv:1603.05620"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of The 28th Conference on Learning Theory. Pages 956\u20131006","author":"Hopkins Samuel B","year":"2015","unstructured":"Samuel B Hopkins, Jonathan Shi, and David Steurer. 2015. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory. Pages 956\u20131006."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmaa.1998.6089"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21398"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a004"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347090"},{"key":"e_1_3_2_1_41_1","volume-title":"Th\u00e9oremes de factorisation dans les espaces r\u00e9ticul\u00e9s. S\u00e9minaire Analyse fonctionnelle (dit\" Maurey-Schwartz\")","author":"Krivine JL","year":"1973","unstructured":"JL Krivine. 1973. Th\u00e9oremes de factorisation dans les espaces r\u00e9ticul\u00e9s. S\u00e9minaire Analyse fonctionnelle (dit\" Maurey-Schwartz\"), 1973. Pages 1\u201322."},{"key":"e_1_3_2_1_42_1","volume-title":"On mean estimation for general norms with statistical queries. arXiv preprint arXiv:1902.02459","author":"Li Jerry","year":"2019","unstructured":"Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. 2019. On mean estimation for general norms with statistical queries. arXiv preprint arXiv:1902.02459, 2019."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm-29-3-275-326"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.46"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02384340"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1874-5849(03)80037-2"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm-58-1-45-90"},{"key":"e_1_3_2_1_48_1","volume-title":"Milman and Gideon Schechtman","author":"Vitali","year":"1986","unstructured":"Vitali D. Milman and Gideon Schechtman. 1986. Asymptotic theory of finite-dimensional normed spaces. Lecture Notes in Mathematics. 1200, Springer-Verlag, Berlin. isbn:3-540-16769-2"},{"key":"e_1_3_2_1_49_1","unstructured":"Andrea Montanari and Emile Richard. 2014. A statistical model for tensor PCA. In Advances in Neural Information Processing Systems. Pages 2897\u20132905."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488618"},{"key":"e_1_3_2_1_51_1","volume-title":"An Approximation Scheme for Quadratic Form Maximization on Convex Bodies","author":"Naor Assaf","year":"2009","unstructured":"Assaf Naor and Gideon Schechtman. 2009. An Approximation Scheme for Quadratic Form Maximization on Convex Bodies. 2009."},{"key":"e_1_3_2_1_52_1","volume-title":"Semidefinite relaxation and nonconvex quadratic optimization. Optimization methods and software, 9, 1-3","author":"Nesterov Yurii","year":"1998","unstructured":"Yurii Nesterov. 1998. Semidefinite relaxation and nonconvex quadratic optimization. Optimization methods and software, 9, 1-3, 1998. Pages 141\u2013160."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(78)90038-1"},{"key":"e_1_3_2_1_54_1","first-page":"1","article-title":"Un th\u00e9or\\`eme sur les op\u00e9rateurs lin\u00e9aires entre espaces de Banach qui se factorisent par un espace de","volume":"13","author":"Pisier Gilles","year":"1980","unstructured":"Gilles Pisier. 1980. Un th\u00e9or\\`eme sur les op\u00e9rateurs lin\u00e9aires entre espaces de Banach qui se factorisent par un espace de Hilbert. Ann. Sci. \\'Ecole Norm. Sup. (4), 13, 1, 1980. Pages 23\u201343. issn:0012-9593 http:\/\/www.numdam.org\/item?id=ASENS_1980_4_13_1_23_0","journal-title":"Hilbert. Ann. Sci. \\'Ecole Norm. Sup. (4)"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Gilles Pisier. 1986. Factorization of linear operators and geometry of Banach spaces. American Mathematical Soc..","DOI":"10.1090\/cbms\/060"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-2011-01348-9"},{"key":"e_1_3_2_1_57_1","volume-title":"Strongly Refuting Random CSPs Below the Spectral Threshold. arXiv preprint arXiv:1605.00058","author":"Raghavendra Prasad","year":"2016","unstructured":"Prasad Raghavendra, Satish Rao, and Tselil Schramm. 2016. Strongly Refuting Random CSPs Below the Spectral Threshold. arXiv preprint arXiv:1605.00058, 2016."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.58"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_1_60_1","first-page":"4","article-title":"Quantum XOR games","volume":"7","author":"Regev Oded","year":"2015","unstructured":"Oded Regev and Thomas Vidick. 2015. Quantum XOR games. ACM Transactions on Computation Theory (ToCT), 7, 4, 2015. Pages 15.","journal-title":"ACM Transactions on Computation Theory (ToCT)"},{"volume-title":"Functional analysis","author":"Rudin Walter","key":"e_1_3_2_1_61_1","unstructured":"Walter Rudin. 1973. Functional analysis. McGraw-Hill Book Co., New York-D\u00fcsseldorf-Johannesburg."},{"key":"e_1_3_2_1_62_1","unstructured":"Zhao Song Ruosong Wang Lin Yang Hongyang Zhang and Peilin Zhong. 2019. Efficient symmetric norm regression via linear sketching. In Advances in Neural Information Processing Systems. Pages 830\u2013840."},{"key":"e_1_3_2_1_63_1","unstructured":"Zhao Song David Woodruff and Peilin Zhong. 2019. Towards a zero-one law for column subset selection. In Advances in Neural Information Processing Systems. Pages 6123\u20136134."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451128","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451128","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":63,"alternative-id":["10.1145\/3406325.3451128","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451128","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}