Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
Show others and affiliations
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
Abstract [en]

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.
Keyword [en]
hardness of approximation, hypergraph coloring, short code
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-205167DOI: 10.1137/140995520ISI: 000396677400005ScopusID: 2-s2.0-85014495830OAI: oai:DiVA.org:kth-205167DiVA: diva2:1088341
Note

QC 20170412

Available from: 2017-04-12 Created: 2017-04-12 Last updated: 2017-04-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
SIAM journal on computing (Print)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 3 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf