Sangxia Huang

activity

20102023

most citedSemi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

5 citations · 7 across the 8 of their papers we have counts for

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2015★ 1 cited

$2^{(l o g N)^{1/10 - o (1)}}$ Hardness for Hypergraph Coloring

Sangxia Huang

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(l o g N)^{1/10 - o (1)}}$ colors, where $N$ is the number of vertices. There has been much focus o…

cs.CC2013

Improved Hardness of Approximating Chromatic Number

Sangxia Huang

We prove that for sufficiently large K, it is NP-hard to color K-colorable graphs with less than 2^{K^{1/3}} colors. This improves the previous result of K versus K^{O(log K)} in K…

cs.CC2010

From Holant To #CSP And Back: Dichotomy For Holant $^{c}$ Problems

Jin-Yi Cai, Sangxia Huang, Pinyan Lu

We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-color…

2(logN)1/10−o(1) Hardness for Hypergraph Coloring

Improved Hardness of Approximating Chromatic Number

From Holant To #CSP And Back: Dichotomy For Holantc Problems

$2^{(l o g N)^{1/10 - o (1)}}$ Hardness for Hypergraph Coloring

From Holant To #CSP And Back: Dichotomy For Holant $^{c}$ Problems