All reports by Author Sangxia Huang:

__
TR15-062
| 15th April 2015
__

Sangxia Huang#### $2^{(\log N)^{1/4-o(1)}}$ Hardness for Hypergraph Coloring

Revisions: 2

__
TR12-040
| 17th April 2012
__

Sangxia Huang#### Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity

Sangxia Huang

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 >>>

Sangxia Huang

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 >>>