HTTP/2 200 server: GitHub.com content-type: text/html; charset=utf-8 last-modified: Thu, 18 Dec 2025 14:04:00 GMT access-control-allow-origin: * strict-transport-security: max-age=31556952 etag: W/"694409d0-1c89" expires: Wed, 31 Dec 2025 03:00:37 GMT cache-control: max-age=600 content-encoding: gzip x-proxy-cache: MISS x-github-request-id: 0C1A:36A0B4:AA8F23:BFE0D7:69548F7D accept-ranges: bytes age: 0 date: Wed, 31 Dec 2025 02:50:37 GMT via: 1.1 varnish x-served-by: cache-bom-vanm7210030-BOM x-cache: MISS x-cache-hits: 0 x-timer: S1767149437.491052,VS0,VE215 vary: Accept-Encoding x-fastly-request-id: cd1a6cf69f1f48cce09fe4da4af31c88df059464 content-length: 2064

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

• Spring 2024: [CMSC 27410 / Math 28410] Honors Combinatorics
• Autumn 2022: [MPCS 50103] Discrete Mathematics for Computer Science
• Autumn 2019, Autumn 2020, Winter 2021, Autumn 2021, Winter 2022: [CMSC 27100] Discrete Mathematics
• Winter 2020: [CMSC 27200] Theory of Algorithms
• Winter 2019, Winter 2023, Winter 2024: [CMSC 27230] Honors Theory of Algorithms
• Autumn 2018: [CMSC 23300] Networks and Distributed Systems

---

Contact

E-mail: nengh at umich dot edu

---

Last updated: Dec 18, 2025