{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:45Z","timestamp":1772313225393,"version":"3.50.1"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"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-1422045,CCF-1526092,CCF-1908125,NSF GRFP"],"award-info":[{"award-number":["CCF-1422045,CCF-1526092,CCF-1908125,NSF GRFP"]}],"id":[{"id":"10.13039\/100000001","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":[[2021,7,31]]},"abstract":"<jats:p>The Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture.<\/jats:p>\n          <jats:p>\n            This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an \u201calmost Unique\u201d version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we call\n            <jats:italic>V Label Cover<\/jats:italic>\n            . Assuming a conjecture concerning the inapproximability of V Label Cover on perfectly satisfiable instances, we prove the following implications:\n          <\/jats:p>\n          <jats:p>\n            \u2022 There is an absolute constant\n            <jats:italic>c<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            such that for\n            <jats:italic>k<\/jats:italic>\n            \u2265 3, given a satisfiable instance of Boolean\n            <jats:italic>k<\/jats:italic>\n            -CSP, it is hard to find an assignment satisfying more than\n            <jats:italic>c<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/2\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            fraction of the constraints.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Given a\n            <jats:italic>k<\/jats:italic>\n            -uniform hypergraph,\n            <jats:italic>k<\/jats:italic>\n            \u2265 2, for all \u03b5 &gt; 0, it is hard to tell if it is\n            <jats:italic>q<\/jats:italic>\n            -strongly colorable or has no independent set with an \u03b5 fraction of vertices, where\n            <jats:italic>q<\/jats:italic>\n            =\u2308\n            <jats:italic>k<\/jats:italic>\n            +\u221a\n            <jats:italic>k<\/jats:italic>\n            -1\/2\u2309.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Given a\n            <jats:italic>k<\/jats:italic>\n            -uniform hypergraph,\n            <jats:italic>k<\/jats:italic>\n            \u2265 3, for all \u03b5 &gt; 0, it is hard to tell if it is (\n            <jats:italic>k<\/jats:italic>\n            -1)-rainbow colorable or has no independent set with an \u03b5 fraction of vertices.\n          <\/jats:p>","DOI":"10.1145\/3459668","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The Quest for Strong Inapproximability Results with Perfect Completeness"],"prefix":"10.1145","volume":"17","author":[{"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Venkat Anantharam Amin Gohari Sudeep Kamath and Chandra Nair. 2013. On maximal correlation hypercontractivity and the data processing inequality studied by Erkip and Cover. arXiv:1304.6133 [cs math].  Venkat Anantharam Amin Gohari Sudeep Kamath and Chandra Nair. 2013. On maximal correlation hypercontractivity and the data processing inequality studied by Erkip and Cover. arXiv:1304.6133 [cs math].","DOI":"10.1109\/ISIT.2014.6875389"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0272-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.23"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_22"},{"key":"e_1_2_1_5_1","volume-title":"10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Avrim Blum (Ed.)","volume":"124","author":"Barak Boaz","year":"2018","unstructured":"Boaz Barak , Pravesh K. Kothari , and David Steurer . 2018 . Small-set expansion in shortcode graph and the 2-to-2 conjecture . In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Avrim Blum (Ed.) , Vol. 124 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 9, 12 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS. 2019.9 10.4230\/LIPIcs.ITCS.2019.9 Boaz Barak, Pravesh K. Kothari, and David Steurer. 2018. Small-set expansion in shortcode graph and the 2-to-2 conjecture. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Avrim Blum (Ed.), Vol. 124. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 9, 12 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.9"},{"key":"e_1_2_1_6_1","volume-title":"34th Computational Complexity Conference (CCC 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Amir Shpilka (Ed.)","volume":"137","author":"Bhangale Amey","year":"2019","unstructured":"Amey Bhangale and Subhash Khot . 2019 . UG-hardness to NP-hardness by losing half . In 34th Computational Complexity Conference (CCC 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Amir Shpilka (Ed.) , Vol. 137 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 3, 20 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CCC. 2019.3 10.4230\/LIPIcs.CCC.2019.3 Amey Bhangale and Subhash Khot. 2019. UG-hardness to NP-hardness by losing half. In 34th Computational Complexity Conference (CCC 2019) (Leibniz International Proceedings in Informatics (LIPIcs)), Amir Shpilka (Ed.), Vol. 137. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 3, 20 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2019.3"},{"key":"e_1_2_1_7_1","volume-title":"37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Bhangale Amey","unstructured":"Amey Bhangale , Subhash Khot , and Devanathan Thiruvenkatachari . 2018. An improved dictatorship test with perfect completeness . In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) (Leibniz International Proceedings in Informatics (LIPIcs)) , S. Lokam and R. Ramanujam (Eds.), Vol. 93 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 15, 23 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.15 10.4230\/LIPIcs.FSTTCS.2017.15 Amey Bhangale, Subhash Khot, and Devanathan Thiruvenkatachari. 2018. An improved dictatorship test with perfect completeness. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), S. Lokam and R. Ramanujam (Eds.), Vol. 93. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 15, 23 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.15"},{"key":"e_1_2_1_8_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Bhattiprolu Vijay V. S. P.","unstructured":"Vijay V. S. P. Bhattiprolu , Venkatesan Guruswami , and Euiwoong Lee . 2015. Approximate hypergraph coloring under low-discrepancy and related promises . In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques , M. Goemans, K. Jansen, J. D. P. Rolim, and L. Trevisan (Eds.). Springer , 152\u2013174. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.152 10.4230\/LIPIcs.APPROX-RANDOM.2015.152 Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. 2015. Approximate hypergraph coloring under low-discrepancy and related promises. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, M. Goemans, K. Jansen, J. D. P. Rolim, and L. Trevisan (Eds.). Springer, 152\u2013174. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.152"},{"key":"e_1_2_1_9_1","volume-title":"31st Conference on Computational Complexity (CCC 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.)","volume":"50","author":"Brakensiek Joshua","year":"2016","unstructured":"Joshua Brakensiek and Venkatesan Guruswami . 2016 . New hardness results for graph and hypergraph colorings . In 31st Conference on Computational Complexity (CCC 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.) , Vol. 50 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 14, 27 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CCC. 2016.14 10.4230\/LIPIcs.CCC.2016.14 Joshua Brakensiek and Venkatesan Guruswami. 2016. New hardness results for graph and hypergraph colorings. In 31st Conference on Computational Complexity (CCC 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Ran Raz (Ed.), Vol. 50. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 14, 27 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.14"},{"key":"e_1_2_1_10_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Brakensiek Joshua","unstructured":"Joshua Brakensiek and Venkatesan Guruswami . 2017. The quest for strong inapproximability results with perfect completeness . In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques , M. Goemans, K. Jansen, J. D. P. Rolim, and L. Trevisan (Eds.). Springer , Article 4, 20 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.4 10.4230\/LIPIcs.APPROX-RANDOM.2017.4 Joshua Brakensiek and Venkatesan Guruswami. 2017. The quest for strong inapproximability results with perfect completeness. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, M. Goemans, K. Jansen, J. D. P. Rolim, and L. Trevisan (Eds.). Springer, Article 4, 20 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.4"},{"key":"e_1_2_1_11_1","unstructured":"Jonah Brown-Cohen and Prasad Raghavendra. 2015. Combinatorial optimization algorithms via polymorphisms. arXiv:1501.01598. http:\/\/arxiv.org\/abs\/1501.01598.  Jonah Brown-Cohen and Prasad Raghavendra. 2015. Combinatorial optimization algorithms via polymorphisms. arXiv:1501.01598. http:\/\/arxiv.org\/abs\/1501.01598."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488665"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541893"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188806"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188804"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100380458"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1458645.1458647"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/120865094"},{"key":"e_1_2_1_24_1","first-page":"6","article-title":"Das statistische Problem der Korrelation als Variations\u2014und Eigenwertproblem und sein Zusammenhang mit der Ausgleichsrechnung","volume":"21","author":"Gebelein Hans","year":"1941","unstructured":"Hans Gebelein . 1941 . Das statistische Problem der Korrelation als Variations\u2014und Eigenwertproblem und sein Zusammenhang mit der Ausgleichsrechnung . ZAMM: Journal of Applied Mathematics and Mechanics\/Zeitschrift f\u00fcr Angewandte Mathematik und Mechanik 21 , 6 (Jan. 1941), 364\u2013379. DOI:https:\/\/doi.org\/10.1002\/zamm.19410210604 10.1002\/zamm.19410210604 Hans Gebelein. 1941. Das statistische Problem der Korrelation als Variations\u2014und Eigenwertproblem und sein Zusammenhang mit der Ausgleichsrechnung. ZAMM: Journal of Applied Mathematics and Mechanics\/Zeitschrift f\u00fcr Angewandte Mathematik und Mechanik 21, 6 (Jan. 1941), 364\u2013379. DOI:https:\/\/doi.org\/10.1002\/zamm.19410210604","journal-title":"ZAMM: Journal of Applied Mathematics and Mechanics\/Zeitschrift f\u00fcr Angewandte Mathematik und Mechanik"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377165"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1070682"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3383-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737729"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201917)","author":"Guruswami Venkatesan","year":"2017","unstructured":"Venkatesan Guruswami and Rishi Saket . 2017 . Hardness of rainbow coloring hypergraphs . In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201917) . Venkatesan Guruswami and Rishi Saket. 2017. Hardness of rainbow coloring hypergraphs. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201917)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a011"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming. 956\u2013968","author":"Hast Gustav","year":"2005","unstructured":"Gustav Hast . 2005 . Approximating Max -CSP\u2014Outperforming a random assignment with almost a linear factor . In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming. 956\u2013968 . Gustav Hast. 2005. Approximating Max -CSP\u2014Outperforming a random assignment with almost a linear factor. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming. 956\u2013968."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_36_1","volume-title":"Query efficient PCPs with perfect completeness. Theory of Computing 1 (Sept","author":"H\u00e5stad Johan","year":"2005","unstructured":"Johan H\u00e5stad and Subhash Khot . 2005. Query efficient PCPs with perfect completeness. Theory of Computing 1 (Sept . 2005 ), 119\u2013148. DOI:https:\/\/doi.org\/10.4086\/toc.2005.v001a007 10.4086\/toc.2005.v001a007 Johan H\u00e5stad and Subhash Khot. 2005. Query efficient PCPs with perfect completeness. Theory of Computing 1 (Sept. 2005), 119\u2013148. DOI:https:\/\/doi.org\/10.4086\/toc.2005.v001a007"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100013517"},{"key":"e_1_2_1_38_1","first-page":"40","article-title":"Approximation resistance on satisfiable instances for predicates strictly dominating parity","volume":"19","author":"Huang Sangxia","year":"2012","unstructured":"Sangxia Huang . 2012 . Approximation resistance on satisfiable instances for predicates strictly dominating parity . Electronic Colloquium on Computational Complexity 19 (2012), 40 . http:\/\/eccc.hpi-web.de\/report\/2012\/040. Sangxia Huang. 2012. Approximation resistance on satisfiable instances for predicates strictly dominating parity. Electronic Colloquium on Computational Complexity 19 (2012), 40. http:\/\/eccc.hpi-web.de\/report\/2012\/040.","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a014"},{"key":"e_1_2_1_40_1","unstructured":"Sangxia Huang. 2015. $2(\\log N)1\/10-o(1)}}$ hardness for hypergraph coloring. arXiv:1504.03923 [cs].  Sangxia Huang. 2015. $2(\\log N)1\/10-o(1)}}$ hardness for hypergraph coloring. arXiv:1504.03923 [cs]."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/120882718"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00023-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902)","author":"Khot Subhash","year":"2002","unstructured":"Subhash Khot . 2002 . On the power of unique 2-prover 1-round games . In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902) . 767\u2013775. Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902). 767\u2013775."},{"key":"e_1_2_1_45_1","volume-title":"Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?SIAM Journal on Computing 37, 1","author":"Khot Subhash","year":"2007","unstructured":"Subhash Khot , Guy Kindler , Elchanan Mossel , and Ryan O\u2019Donnell . 2007. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?SIAM Journal on Computing 37, 1 ( 2007 ), 319\u2013357. DOI:https:\/\/doi.org\/10.1137\/S0097539705447372 10.1137\/S0097539705447372 Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O\u2019Donnell. 2007. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?SIAM Journal on Computing 37, 1 (2007), 319\u2013357. DOI:https:\/\/doi.org\/10.1137\/S0097539705447372"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055432"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Khot S.","year":"2018","unstructured":"S. Khot , D. Minzer , and M. Safra . 2018. Pseudorandom sets in Grassmann graph have near-perfect expansion . In Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918) . 592\u2013601. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2018 .00062 10.1109\/FOCS.2018.00062 S. Khot, D. Minzer, and M. Safra. 2018. Pseudorandom sets in Grassmann graph have near-perfect expansion. In Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918). 592\u2013601. DOI:https:\/\/doi.org\/10.1109\/FOCS.2018.00062"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science. 206\u2013215","author":"Khot Subhash","year":"2014","unstructured":"Subhash Khot and Rishi Saket . 2014 . Hardness of coloring 2-colorable 12-uniform hypergraphs with ith colors . In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science. 206\u2013215 . Subhash Khot and Rishi Saket. 2014. Hardness of coloring 2-colorable 12-uniform hypergraphs with ith colors. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science. 206\u2013215."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.117"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746549"},{"key":"e_1_2_1_52_1","unstructured":"Euiwoong Lee. 2016. Improved hardness for cut interdiction and firefighter problems. arXiv:1607.05133. http:\/\/arxiv.org\/abs\/1607.05133.  Euiwoong Lee. 2016. Improved hardness for cut interdiction and firefighter problems. arXiv:1607.05133. http:\/\/arxiv.org\/abs\/1607.05133."},{"key":"e_1_2_1_53_1","volume-title":"Approximation algorithm for non-Boolean Max--CSP. Theory of Computing 10 (Oct","author":"Makarychev Konstantin","year":"2014","unstructured":"Konstantin Makarychev and Yury Makarychev . 2014. Approximation algorithm for non-Boolean Max--CSP. Theory of Computing 10 (Oct . 2014 ), 341\u2013358. DOI:https:\/\/doi.org\/10.4086\/toc.2014.v010a013 10.4086\/toc.2014.v010a013 Konstantin Makarychev and Yury Makarychev. 2014. Approximation algorithm for non-Boolean Max--CSP. Theory of Computing 10 (Oct. 2014), 341\u2013358. DOI:https:\/\/doi.org\/10.4086\/toc.2014.v010a013"},{"key":"e_1_2_1_54_1","volume-title":"A random recolouring method for graphs and hypergraphs. Combinatorics, Probability and Computing 2 (Sept","author":"McDiarmid Colin","year":"1993","unstructured":"Colin McDiarmid . 1993. A random recolouring method for graphs and hypergraphs. Combinatorics, Probability and Computing 2 (Sept . 1993 ), 363\u2013365. DOI:https:\/\/doi.org\/10.1017\/S0963548300000730 10.1017\/S0963548300000730 Colin McDiarmid. 1993. A random recolouring method for graphs and hypergraphs. Combinatorics, Probability and Computing 2 (Sept. 1993), 363\u2013365. DOI:https:\/\/doi.org\/10.1017\/S0963548300000730"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0047-x"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.295"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374458"},{"key":"e_1_2_1_58_1","volume-title":"Analysis of Boolean functions","author":"O\u2019Donnell Ryan","unstructured":"Ryan O\u2019Donnell . 2014. Analysis of Boolean functions . Cambridge University Press . Ryan O\u2019Donnell. 2014. Analysis of Boolean functions. Cambridge University Press."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536482"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024507"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.30"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.16"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/070681612"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743425"},{"key":"e_1_2_1_68_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Tamaki Suguru","unstructured":"Suguru Tamaki and Yuichi Yoshida . 2010. A query efficient non-adaptive long code test with perfect completeness . In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques . Springer , 738\u2013751. DOI:https:\/\/doi.org\/10.1007\/978-3-642-15369-3_55 10.1007\/978-3-642-15369-3_55 Suguru Tamaki and Yuichi Yoshida. 2010. A query efficient non-adaptive long code test with perfect completeness. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Springer, 738\u2013751. DOI:https:\/\/doi.org\/10.1007\/978-3-642-15369-3_55"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009209"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010035"},{"key":"e_1_2_1_71_1","unstructured":"Girish Varma. 2014. Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. arXiv:1408.0262 [cs]. http:\/\/arxiv.org\/abs\/1408.0262.  Girish Varma. 2014. Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. arXiv:1408.0262 [cs]. http:\/\/arxiv.org\/abs\/1408.0262."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a023"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/0128010"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459668","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459668","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459668","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:50Z","timestamp":1750193330000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459668"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":72,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3459668"],"URL":"https:\/\/doi.org\/10.1145\/3459668","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}