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
Improved Approximation Algorithms for Multiway Cut by Large
Mixtures of New and Old Rounding Schemes Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick [arXiv][conference (STOC 26)]
MAX BISECTION Might be Harder to Approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick [arXiv][conference (SODA 26)]
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
Ian DeHaan, Neng Huang, Euiwoong Lee [arXiv][conference (APPROX 25)]
Hardness of Sampling for the Anti-ferromagnetic Ising Model on Random Graphs
Neng Huang, Will Perkins, Aaron Potechin [arXiv][conference (ITCS 25)]
Tight Approximability of MAX 2-SAT and Relatives, Under UGC
Joshua Brakensiek, Neng Huang, Uri Zwick [arXiv][conference (SODA 24)]
Separating MAX 2-AND, MAX DI-CUT and MAX CUT Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick [arXiv][conference (FOCS 23)]
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 [arXiv][Journal (Proceedings of the Royal Society A)]
On the Decision Tree Complexity of String Matching Xiaoyu He, Neng Huang, Xiaoming Sun [arXiv][conference (ESA 18)]
Manuscripts
Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs Nikhil Bansal, Neng Huang, Euiwoong Lee [arXiv][In submission]
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]
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
