{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T05:10:05Z","timestamp":1777957805764,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,2,8]],"date-time":"2017-02-08T00:00:00Z","timestamp":1486512000000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["Career Award,0832797"],"award-info":[{"award-number":["Career Award,0832797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,8]]},"abstract":"\n The Unique Games Conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for\n none<\/jats:italic>\n of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance nevertheless seems critical in these proofs. In this work, we bypass the need for UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case.\n <\/jats:p>\n \n The first problem, known as\n \n L\n p<\/jats:sub>\n <\/jats:italic>\n Subspace Approximation, is a generalization of the classic least squares regression problem. Here, the input consists of a set of points\n X<\/jats:italic>\n = {\u03b1\n 1<\/jats:sub>\n , \u2026 , \u03b1\n m<\/jats:sub>\n } \u2286 R\n \n n<\/jats:sub>\n <\/jats:italic>\n and a parameter\n k<\/jats:italic>\n (possibly depending on\n n<\/jats:italic>\n ). The goal is to find a subspace\n H<\/jats:italic>\n of\n R<\/jats:italic>\n \n n<\/jats:sub>\n <\/jats:italic>\n of dimension\n k<\/jats:italic>\n that minimizes the \u2113\n \n p<\/jats:italic>\n <\/jats:sub>\n norm of the Euclidean distances to the points in\n X<\/jats:italic>\n . For\n p<\/jats:italic>\n = 2,\n k<\/jats:italic>\n =\n n<\/jats:italic>\n \u2212 1, this reduces to the least squares regression problem, while for\n p<\/jats:italic>\n = \u221e,\n k<\/jats:italic>\n = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed\n p<\/jats:italic>\n \u2208 (2, \u221e), and for\n k<\/jats:italic>\n =\n n<\/jats:italic>\n \u2212 1, it is NP-hard to approximate this problem to within a factor of \u03b3\n \n p<\/jats:italic>\n <\/jats:sub>\n \u2212 \u03f5 for constant \u03f5 > 0, where \u03b3\n \n p<\/jats:italic>\n <\/jats:sub>\n is the\n p<\/jats:italic>\n th norm of a standard Gaussian random variable. This matches the \u03b3\n \n p<\/jats:italic>\n <\/jats:sub>\n approximation algorithm obtained by Deshpande, Tulsiani, and Vishnoi who also showed the same hardness result under the UGC.\n <\/jats:p>\n \n The second problem we study is the related\n \n L\n p<\/jats:sub>\n <\/jats:italic>\n Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor, and Schechtman. Here, the input is a multilinear quadratic form \u2211\n \n n<\/jats:italic>\n <\/jats:sub>\n \n i<\/jats:italic>\n ,\n j<\/jats:italic>\n = 1\n <\/jats:sub>\n \n a\n ij<\/jats:sub>\n x\n i<\/jats:sub>\n x\n j<\/jats:sub>\n <\/jats:italic>\n and the goal is to maximize the quadratic form over the \u2113\n \n p<\/jats:italic>\n <\/jats:sub>\n unit ball, namely, all\n x<\/jats:italic>\n with \u2211\n \n n<\/jats:italic>\n <\/jats:sub>\n \n i<\/jats:italic>\n = 1\n <\/jats:sub>\n |\n \n x\n i<\/jats:sub>\n <\/jats:italic>\n |\n \n p<\/jats:italic>\n <\/jats:sub>\n \u2a7d 1. The problem is polynomial time solvable for\n p<\/jats:italic>\n = 2. We show that for any constant\n p<\/jats:italic>\n \u2208 (2, \u221e), it is NP-hard to approximate the quadratic form to within a factor of \u03b3\n 2<\/jats:sub>\n \n p<\/jats:italic>\n <\/jats:sub>\n \u2212 \u03f5 for any \u03f5 > 0. The same hardness factor was shown under the UGC by Kindler et al. We also obtain a \u03b3\n 2<\/jats:sub>\n \n p<\/jats:italic>\n <\/jats:sub>\n -approximation algorithm for the problem using the convex relaxation of the problem defined by Kindler et al. A \u03b3\n 2<\/jats:sub>\n \n p<\/jats:italic>\n <\/jats:sub>\n approximation algorithm has also been independently obtained by Naor and Schechtman.\n <\/jats:p>\n \n These are the\n first<\/jats:italic>\n approximation thresholds, proven under P \u2260 NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves do not explicitly involve the Gaussian distribution.\n <\/jats:p>","DOI":"10.1145\/2737729","type":"journal-article","created":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T17:37:07Z","timestamp":1454953027000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Bypassing UGC from Some Optimal Geometric Inapproximability Results"],"prefix":"10.1145","volume":"12","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Forbes Avenue, Pittsburgh PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rishi","family":"Saket","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Wu","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-005-0465-9"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441629"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.57"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_2_1_9_1","volume-title":"Numerical Optimization: Continuous and Discrete Problems.","author":"Brieden A.","year":"2000","unstructured":"A. Brieden, P. Gritzman, and V. Klee. 2000. Inapproximability of some geometric and quadratic optimization problems. In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.39"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133075"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250884"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873654"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748055"},{"key":"e_1_2_1_15_1","volume-title":"Matrix Computations","author":"Golub G.","unstructured":"G. Golub and C. van Loan. 1996. Matrix Computations. Johns Hopkins University Press."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/070705258"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513440"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652134"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0425"},{"key":"e_1_2_1_27_1","volume-title":"Approximation, Singular Integral Operators, and Related Topics,Vol.129","author":"Megretski A.","unstructured":"A. Megretski. 2001. Relaxations of quadratic programs in operator theory and system analysis. Systems, Approximation, Singular Integral Operators, and Related Topics,Vol.129. Springer Basel AG, 365--392."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0047-x"},{"key":"e_1_2_1_29_1","unstructured":"A. Naor and G. Schechtman. 2010. An approximation scheme for quadratic form maximization on convex bodies. Preprint."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"A. Nemirovski C. Roos and T. Terlaky. 1999. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program. 86 3 Ser. A (1999) 463--473.","DOI":"10.1007\/s101070050100"},{"key":"e_1_2_1_31_1","volume-title":"CORE","author":"Nesetrov Y.","year":"1998","unstructured":"Y. Nesetrov. 1998. Global quadratic optimization via conic relaxation. Working Paper, CORE (1998)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283440"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/050627472"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.314701"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2737729","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2737729","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2737729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:25:06Z","timestamp":1763457906000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2737729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,8]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,8]]}},"alternative-id":["10.1145\/2737729"],"URL":"https:\/\/doi.org\/10.1145\/2737729","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,8]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}