We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... more >>>

In this paper, we study the approximability of Max CSP($P$) where $P$ is a Boolean predicate. We prove that assuming Khot's $d$-to-1 Conjecture, if the set of accepting inputs of $P$ strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate Max CSP($P$) better than ... more >>>