Sangxia Huang

I received my PhD in 2015 from KTH Royal Institute of Technology, where I was extremely fortunate to be advised by Prof. Johan Håstad. I then did a postdoc at EPFL, under the supervision of Prof. Ola Svensson.

I did my undergraduate studies at Shanghai Jiao Tong University. I had also worked as an intern student at Theory Group of Microsoft Research Asia, supervised by Prof. Pinyan Lu. During the fall semester of 2013, I visited Prof. Ryan O'Donnell at Carnegie Mellon University. I also did a summer internship at Toyota Technological Institute at Chicago with Prof. Madhur Tulsiani June - August, 2014.

Publications

• Adversarial Attacks and Defences Competition, with Alexey Kurakin, Ian Goodfellow, Samy Bengio, et.al. 2018.
• Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering, with Buddhima Gamlath and Ola Svensson. To appear in ICALP 2018.
• Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits, with Abbas Bazzi, Samuel Fiorini and Ola Svensson. SODA 2017.
• 2^{(log N)1/10-o(1)} Hardness for Hypergraph Coloring. Manuscript.
• Improved NP-inapproximability for 2-variable linear equations, with Johan Håstad, Rajsekar Manokaran, Ryan O'Donnell and John Wright. Theory of Computing 13(19), 2017. Preliminary version in APPROX 2015.
• Improved Hardness of Approximating Chromatic Number. APPROX 2013.
• Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs. Theory of Computing 10(14), 2014, 359--388. Preliminary version in STOC 2013.
• A Dichotomy for Real Weighted Holant Problems, with Pinyan Lu. Computational Complexity, 2015. Preliminary version in CCC 2012.
• The Complexity of Weighted Boolean #CSP Modulo k, with Heng Guo, Pinyan Lu and Mingji Xia, STACS 2011.
• From Holant To #CSP And Back: Dichotomy For Holant^c Problems, with Jin-Yi Cai and Pinyan Lu, Algorithmica 64(3): 511--533, 2012. Preliminary version in ISAAC 2010 (best paper).

Thesis

• Hardness of Constraint Satisfaction and Hypergraph Coloring: Constructions of Probabilistically Checkable Proofs with Perfect Completeness. PhD Thesis, 2015, Stockholm, Sweden.