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. Hardness of Sampling for the Anti-ferromagnetic Ising Model on Random Graphs
    Neng Huang, Will Perkins, Aaron Potechin
    [arXiv] [conference (ITCS 25)]
  2. Tight Approximability of MAX 2-SAT and Relatives, Under UGC
    Joshua Brakensiek, Neng Huang, Uri Zwick
    [arXiv] [conference (SODA 24)]
  3. Separating MAX 2-AND, MAX DI-CUT and MAX CUT
    Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
    [arXiv] [conference (FOCS 23)]
  4. 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)]
  5. On the Approximability of Presidential Type Predicates
    Neng Huang, Aaron Potechin
    [arXiv] [conference (APPROX 20)]
  6. On the Decision Tree Complexity of String Matching
    Xiaoyu He, Neng Huang, Xiaoming Sun
    [arXiv] [conference (ESA 18)]

Preprints

  1. 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: February 11, 2025