Neng Huang

Hello! I am a sixth-year PhD student in the Department of Computer Science at UChicago, advised by Aaron Potechin. I am on the job market this year.

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

Papers

1. Tight Approximability of MAX 2-SAT and Relatives, Under UGC
   Joshua Brakensiek, Neng Huang, Uri Zwick
   [arXiv] [conference (SODA 24)]
   
2. Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs
   Antares Chen, Neng Huang, Kunal Marwaha
   [arXiv]
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)]
   
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)]
   

Teaching

Teaching Assistant at UChicago

• 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: nenghuang at uchicago dot edu

Last updated: January 23, 2024