Neng Huang

Hello! I am a researcher in theoretical computer science. Previously I was 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

Preprints
  1. Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
    Nikhil Bansal, Neng Huang, Euiwoong Lee
    In submission arXiv
  2. 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 arXiv
2026
  1. Separating MAX 2-AND, MAX DI-CUT and MAX CUT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    SIAM Journal on Computing arXiv
    Special Issue for FOCS 23.
  2. Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP
    Suprovat Ghoshal, Neng Huang, Euiwoong Lee, Konstantin Makarychev, Yury Makarychev
    APPROX arXiv
  3. Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs
    Antares Chen, Neng Huang, Kunal Marwaha
    RANDOM arXiv
  4. Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    STOC arXiv
  5. MAX BISECTION Might be Harder to Approximate than MAX CUT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    SODA arXiv
2025
  1. On the Mysteries of MAX NAE-SAT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    SIAM Journal on Discrete Mathematics arXiv
    Conference version: SODA 21.
  2. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
    Ian DeHaan, Neng Huang, Euiwoong Lee
    APPROX arXiv
  3. Hardness of Sampling for the Anti-ferromagnetic Ising Model on Random Graphs
    Neng Huang, Will Perkins, Aaron Potechin
    ITCS arXiv
2024
  1. Tight Approximability of MAX 2-SAT and Relatives, Under UGC
    Joshua Brakensiek, Neng Huang, Uri Zwick
    SODA arXiv
2020
  1. On the Approximability of Presidential Type Predicates
    Neng Huang, Aaron Potechin
    APPROX arXiv
2019
  1. The idemetric property: when most distances are (almost) the same
    George Barmpalias, Neng Huang, Andrew Lewis-Pye, Angsheng Li, Xuechen Li, Yicheng Pan, Tim Roughgarden
    Proceedings of the Royal Society A arXiv
2018
  1. On the Decision Tree Complexity of String Matching
    Xiaoyu He, Neng Huang, Xiaoming Sun
    ESA arXiv

Teaching

Teaching Assistant at UChicago

Contact

E-mail: nengh at umich dot edu

Last updated: Jul 20, 2026