Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-073 | 21st April 2018 19:27

NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

RSS-Feed




TR18-073
Authors: Amey Bhangale
Publication: 21st April 2018 20:59
Downloads: 1686
Keywords: 


Abstract:

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of NP-hardness, it improves the result of Guruswami, H{\aa}stad and Sudan ~\cite{GHS02}, combined with Moshkovitz-Raz~\cite{MR10}, by an `exponential' factor. The second result improves the result of Saket~\cite{S14} which shows $quasi$-NP-hardness of coloring a $2$-colorable $4$-uniform hypergraph with $O\left(\log^\gamma n\right)$ colors for a sufficiently small constant $1\gg\gamma>0$.

Our result is the first to show the NP-hardness of coloring a $c$-colorable $k$-uniform hypergraph with poly-logarithmically many colors, for $any$ constants $c\geq 2$ and $k\geq 3$.



ISSN 1433-8092 | Imprint