SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES
2017 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 46, no 1, 132-159 p.Article in journal (Refereed) Published
We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the "short code" 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(root loglg n)) colors; coloring a 4-colorable 4-uniform hypergraph with 2(2 Omega(root loglg 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.
Place, publisher, year, edition, pages
SIAM PUBLICATIONS , 2017. Vol. 46, no 1, 132-159 p.
hardness of approximation, hypergraph coloring, short code
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-205167DOI: 10.1137/140995520ISI: 000396677400005ScopusID: 2-s2.0-85014495830OAI: oai:DiVA.org:kth-205167DiVA: diva2:1088341
QC 201704122017-04-122017-04-122017-04-12Bibliographically approved