Neng Huang

Hello! I am a postdoctoral research fellow in the Computer Science and Engineering Division at the University of Michigan, advised by Nikhil Bansal and Euiwoong Lee. I obtained my PhD at the University of Chicago, where I was advised by Aaron Potechin.

I am interested in discrete math and theoretical computer science. I've been working on worst-case approximation algorithms and hardness of approximation for constraint satisfaction problems. Recently, I've also been studying average-case analysis of CSPs.

Papers

Publications

  1. MAX BISECTION Might be Harder to Approximate than MAX CUT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    [arXiv] [conference (SODA 26)]
  2. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
    Ian DeHaan, Neng Huang, Euiwoong Lee
    [arXiv] [conference (APPROX 25)]
  3. Hardness of Sampling for the Anti-ferromagnetic Ising Model on Random Graphs
    Neng Huang, Will Perkins, Aaron Potechin
    [arXiv] [conference (ITCS 25)]
  4. Tight Approximability of MAX 2-SAT and Relatives, Under UGC
    Joshua Brakensiek, Neng Huang, Uri Zwick
    [arXiv] [conference (SODA 24)]
  5. Separating MAX 2-AND, MAX DI-CUT and MAX CUT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    [arXiv] [conference (FOCS 23)]
  6. On the Mysteries of MAX NAE-SAT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    [arXiv] [conference (SODA 21)]
    [Journal (SIAM Journal on Discrete Mathematics)]
  7. On the Approximability of Presidential Type Predicates
    Neng Huang, Aaron Potechin
    [arXiv] [conference (APPROX 20)]
  8. On the Decision Tree Complexity of String Matching
    Xiaoyu He, Neng Huang, Xiaoming Sun
    [arXiv] [conference (ESA 18)]

Manuscripts

  1. Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
    Nikhil Bansal, Neng Huang, Euiwoong Lee
    [In submission]
  2. Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    [In submission]
  3. On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
    Suprovat Ghoshal, Neng Huang, Euiwoong Lee, Konstantin Makarychev, Yury Makarychev
    [In submission]
  4. Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs
    Antares Chen, Neng Huang, Kunal Marwaha
    [arXiv]

Teaching

Teaching Assistant at UChicago

Contact

E-mail: nengh at umich dot edu

Last updated: Dec 18, 2025