{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:57Z","timestamp":1787340417085,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"US-Israel BSF","award":["2008293"],"award-info":[{"award-number":["2008293"]}]},{"name":"Packard Fellowship"},{"name":"Google India PhD Fellowship"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["226203"],"award-info":[{"award-number":["226203"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1115525"],"award-info":[{"award-number":["CCF-1115525"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the \u201cshort code\u201d of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287--1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611--649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on $n$-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with $2^{2^{\\Omega(\\sqrt{\\log \\log n})}}$ colors; coloring a 4-colorable 4-uniform hypergraph with $2^{2^{\\Omega(\\sqrt{\\log \\log n})}}$ colors; and coloring a 3-colorable 3-uniform hypergraph with $(\\log n)^{\\Omega(1\/\\log\\log\\log n)}$ colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, $(\\log n)^{O(1)}$ colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for $O(1)$-colorable hypergraphs, and $(\\log\\log n)^{O(1)}$ for $O(1)$-colorable, 3-uniform hypergraphs.<\/jats:p>","DOI":"10.1137\/140995520","type":"journal-article","created":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T10:05:19Z","timestamp":1487757919000},"page":"132-159","source":"Crossref","is-referenced-by-count":3,"title":["Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes"],"prefix":"10.1137","volume":"46","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prahladh","family":"Harsha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Girish","family":"Varma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"S. Arora and E. Chlamtac,\n                      New approximation guarantee for chromatic number\n                      , in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 215-224,https:\/\/doi.org\/10.1145\/1132516.1132548.","DOI":"10.1145\/1132516.1132548"},{"key":"atypb2","first-page":"425","volume":"3","author":"Alon N.","year":"1996","journal-title":"Nordic J. Comput."},{"key":"atypb3","first-page":"14","author":"Brakensiek J.","year":"2016","journal-title":"CCC."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/130929394"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman,\n                      Optimal testing of Reed-Muller codes\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 488-497,https:\/\/doi.org\/10.1109\/FOCS.2010.54.","DOI":"10.1109\/FOCS.2010.54"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176586"},{"key":"atypb9","first-page":"345","author":"Chen H.","year":"1996","journal-title":"Heidelberg"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"E. Chlamtac,\n                      Approximation algorithms using hierarchies of semidefinite programming relaxations\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007, pp. 691-701,https:\/\/doi.org\/10.1109\/FOCS.2007.72.","DOI":"10.1109\/FOCS.2007.72"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-015-1231-3"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"I. Dinur and G. Kol,\n                      Covering CSPs\n                      , in Proceedings of the 28th IEEE Conference on Computational Complexity, 2013, pp. 207-218,https:\/\/doi.org\/10.1109\/CCC.2013.29.","DOI":"10.1109\/CCC.2013.29"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"V. Guruswami, P. Harsha, J. H\u00e5stad, S. Srinivasan, and G. Varma,\n                      Super-polylogarithmic hypergraph coloring hardness via low-degree long codes\n                      , in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 2014, pp. 614-623,https:\/\/doi.org\/10.1145\/2591796.2591882.","DOI":"10.1145\/2591796.2591882"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377165"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/120879257"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Huang,\n                      Improved hardness of approximating chromatic number\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Lecture Notes in Comput. Sci. 8096, P. Raghavendra, S. Raskhodnikova, K. Jansen, and J. D. P. Rolim, eds., Springer, Berlin, Heidelberg, 2013, pp. 233-243,https:\/\/doi.org\/10.1007\/978-3-642-40328-6_17.","DOI":"10.1007\/978-3-642-40328-6_17"},{"key":"atypb22","unstructured":"S. Huang,\n                      $2^{(\\log N)^{1\/10-o(1)}}$ Hardness for Hypergraph Coloring\n                      , preprint,https:\/\/arxiv.org\/abs\/1504.03923, 2015."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring\n                      , in Proceedings of the $42$nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 600-609,https:\/\/doi.org\/10.1109\/SFCS.2001.959936.","DOI":"10.1109\/SFCS.2001.959936"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      Hardness results for approximate hypergraph coloring\n                      , in Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 351-359,https:\/\/doi.org\/10.1145\/509907.509962.","DOI":"10.1145\/509907.509962"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      Hardness results for coloring 3-colorable 3-uniform hypergraphs\n                      , in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 23-32,https:\/\/doi.org\/10.1109\/SFCS.2002.1181879.","DOI":"10.1109\/SFCS.2002.1181879"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"D. M. Kane and R. Meka,\n                      A PRG for Lipschitz functions of polynomials with applications to sparsest cut\n                      , in Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC), 2013, pp. 1-10,https:\/\/doi.org\/10.1145\/2488608.2488610.","DOI":"10.1145\/2488608.2488610"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1173"},{"key":"atypb31","first-page":"206","author":"Khot S.","year":"2014","journal-title":"Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS)"},{"key":"atypb32","first-page":"68","author":"Kawarabayashi K.","year":"2012","journal-title":"Proceedings of the IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)"},{"key":"atypb33","first-page":"458","author":"Kawarabayashi K.","year":"2014","journal-title":"Germany"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"R. Lidl and H. Niederreiter,\n                      Finite Fields\n                      , 2nd ed., Encyclopedia Math. Appl. 20, Cambridge University Press, Cambridge, UK, 1997,https:\/\/doi.org\/10.1017\/CBO9780511525926.","DOI":"10.1017\/CBO9780511525926"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"R. Saket,\n                      Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable CSPs\n                      , in Proceedings of the 29th IEEE Conference on Computational Complexity, 2014, pp. 78-89,https:\/\/doi.org\/10.1109\/CCC.2014.16.","DOI":"10.1109\/CCC.2014.16"},{"key":"atypb37","first-page":"3","volume":"2015","author":"Varma G.","year":"2015","journal-title":"Chic. J. Theoret. Comput. Sci."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140995520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:11Z","timestamp":1787337251000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140995520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/140995520"],"URL":"https:\/\/doi.org\/10.1137\/140995520","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}