{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:25Z","timestamp":1763468125052,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T00:00:00Z","timestamp":1357689600000},"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":[[2013,1,9]]},"DOI":"10.1145\/2422436.2422460","type":"proceedings-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T12:58:22Z","timestamp":1357217902000},"page":"197-214","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction"],"prefix":"10.1145","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[{"name":"Microsoft Research New England, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kindler","sequence":"additional","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Inapproximability of densest k-subgraph from average case hardness","author":"Alon Noga","year":"2011","unstructured":"Noga Alon , Sanjeev Arora , Rajsekar Manokaran , Dana Moshkovitz , and Omri Weinstein , Inapproximability of densest k-subgraph from average case hardness , 2011 , Manuscript . Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein, Inapproximability of densest k-subgraph from average case hardness, 2011, Manuscript."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.18"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_3_2_2_6_1","first-page":"298","volume-title":"IEEE Computer Society","author":"Alekhnovich Michael","year":"2003","unstructured":"Michael Alekhnovich , More on average case vs approximation complexity, FOCS , IEEE Computer Society , 2003 , pp. 298 -- 307 . Michael Alekhnovich, More on average case vs approximation complexity, FOCS, IEEE Computer Society, 2003, pp. 298--307."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.20"},{"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.1145\/1806689.1806719"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095150"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/188105.188169"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_2_2_13_1","volume-title":"SDP gaps from pairwise independence","author":"Benabbas Siavosh","year":"2012","unstructured":"Siavosh Benabbas , Konstantinos Georgiou , Avner Magen , and Madhur Tulsiani , SDP gaps from pairwise independence , 2012 , Manuscript . Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani, SDP gaps from pairwise independence, 2012, Manuscript."},{"key":"e_1_3_2_2_14_1","first-page":"512","volume-title":"SODA","author":"Barak Boaz","year":"2011","unstructured":"Boaz Barak , Moritz Hardt , Thomas Holenstein , and David Steurer , Subsampling mathematical relaxations and average-case complexity , SODA , SIAM , 2011 , pp. 512 -- 531 . Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer, Subsampling mathematical relaxations and average-case complexity, SODA, SIAM, 2011, pp. 512--531."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"e_1_3_2_2_17_1","first-page":"649","volume-title":"IEEE Computer Society","author":"Bulatov Andrei A.","year":"2002","unstructured":"Andrei A. Bulatov , A dichotomy theorem for constraints on a three-element set, FOCS , IEEE Computer Society , 2002 , pp. 649 -- 658 . Andrei A. Bulatov, A dichotomy theorem for constraints on a three-element set, FOCS, IEEE Computer Society, 2002, pp. 649--658."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873188"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.78"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646753.704904"},{"key":"e_1_3_2_2_22_1","volume-title":"Combinatoricatextbf1","author":"Gr\u00f6tschel Martin","year":"1981","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver , The ellipsoid method and its consequences in combinatorial optimization , Combinatoricatextbf1 ( 1981 ), no. 2, 169--197. Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatoricatextbf1 (1981), no. 2, 169--197."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095174"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_2_2_27_1","first-page":"23","volume-title":"IEEE Computer Society","author":"Khot Subhash","year":"2002","unstructured":"Subhash Khot , Hardness results for coloring 3 -colorable 3 -uniform hypergraphs, FOCS , IEEE Computer Society , 2002 , pp. 23 -- 32 . Subhash Khot, Hardness results for coloring 3 -colorable 3 -uniform hypergraphs, FOCS, IEEE Computer Society, 2002, pp. 23--32."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.49"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.78"},{"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":"The node-deletion problem for hereditary properties is np-complete, J. Comput. Syst. Sci.textbf20","author":"John","year":"1980","unstructured":"John M. Lewis and Mihalis Yannakakis , The node-deletion problem for hereditary properties is np-complete, J. Comput. Syst. Sci.textbf20 ( 1980 ), no. 2, 219--230. John M. Lewis and Mihalis Yannakakis, The node-deletion problem for hereditary properties is np-complete, J. Comput. Syst. Sci.textbf20 (1980), no. 2, 219--230."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_3_2_2_35_1","first-page":"1","article-title":"Noise stability of functions with low influences: invariance and optimality","author":"Mossel E.","year":"2010","unstructured":"E. Mossel , R. O'Donnell , and K. Oleszkiewicz ., Noise stability of functions with low influences: invariance and optimality , Annals of Mathematicstextbf171 ( 2010 ), no. 1 , 295--341. E. Mossel, R. O'Donnell, and K. Oleszkiewicz., Noise stability of functions with low influences: invariance and optimality, Annals of Mathematicstextbf171 (2010), no. 1, 295--341.","journal-title":"Annals of Mathematicstextbf171 ("},{"key":"e_1_3_2_2_36_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC) 18","author":"Moshkovitz Dana","year":"2011","unstructured":"Dana Moshkovitz , The projection games conjecture and the NP-hardness of ln n-approximating set-cover , Electronic Colloquium on Computational Complexity (ECCC) 18 ( 2011 ), 112. Dana Moshkovitz, The projection games conjecture and the NP-hardness of ln n-approximating set-cover, Electronic Colloquium on Computational Complexity (ECCC) 18 (2011), 112."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.60"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.74"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"}],"event":{"name":"ITCS '13: Innovations in Theoretical Computer Science","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Berkeley California USA","acronym":"ITCS '13"},"container-title":["Proceedings of the 4th conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422460","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2422436.2422460","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:14Z","timestamp":1750277654000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422460"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,9]]},"references-count":45,"alternative-id":["10.1145\/2422436.2422460","10.1145\/2422436"],"URL":"https:\/\/doi.org\/10.1145\/2422436.2422460","relation":{},"subject":[],"published":{"date-parts":[[2013,1,9]]},"assertion":[{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}