Yuhao Li (李毓浩)
I am a fifth-year (2021-present) PhD student in the theory group at Columbia University, honored to be advised by Prof. Xi Chen and Prof. Rocco Servedio. Starting from my PhD, I am also extremely fortunate to closely collaborate with Prof. Toniann Pitassi and Prof. Mihalis Yannakakis.
Prior to that, I got a B.Sc. degree in computer science from Peking University, where I was extremely fortunate to be advised by Prof. Xiaotie Deng on algorithmic game theory.
I am broadly interested in theoretical computer science and discrete mathematics, including complexity theory (TFNP, proof complexity, communication complexity), game theory, logic and automata theory, and combinatorics.
News
Jan 2026
Our paper joint with Hanlin and Jiawei, Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds, was accepted to STOC 2026.
Nov 2025
Our paper with Xi Chen, Constant Inapproximability of Pacing Equilibria in Second-Price Auctions, was accepted to WINE 2025 and won an Outstanding Paper Award!
Oct 2025
I gave talks at theory seminars at Rutgers, UPenn, CMU, Columbia, and MIT. Enjoyed the visits!
Aug 2025
Our paper Reducing Tarski to Unique Tarski (in the Black-box Model) was accepted by SICOMP.
Jun 2025
I presented Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds (joint work with Hanlin and Jiawei) at the STOC 2025 TFNP Workshop. Check out a new refuter problem!
May 2025
Two papers were accepted to EC 2025.
Apr 2025
Our work Computing a Fixed Point of Contraction Maps in Polynomial Queries was invited to HALG 2025.
Mar 2025
Our paper Computing a Fixed Point of Contraction Maps in Polynomial Queries was accepted by JACM (see also an improved bound in the newest version).