Yuhao Li (李毓浩)

Yuhao Li

I am a third-year (2021-present) PhD student in the theory group of Computer Science Department, Columbia University. I am extremely fortunate to be advised by Prof. Xi Chen and Prof. Rocco Servedio. Prior to that, I got the B.Sc. degree in computer science from Peking University, where I was fortunate to be advised by Prof. Xiaotie Deng on algorithmic game theory.

My research interests broadly lie in theoretical computer science, especially algorithms and complexity theory related to TFNP, proof complexity, communication complexity, and property testing.



  • Computing a Fixed Point of Contraction Maps in Polynomial Queries
  • Intersection Classes in TFNP and Proof Complexity
  • Testing Intersecting and Union-Closed Families (arXiv)
  • Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas (arXiv)
  • 2023

  • MEV Makes Everyone Happy under Greedy Sequencing Rule (arXiv, CCS DeFi)
  • Reducing Tarski to Unique Tarski (in the Black-box Model) (ECCC, CCC)
  • 2022

  • Optimal Private Payoff Manipulation against Commitment in Extensive-form Games (arXiv)
  • Insightful Mining Equilibria (arXiv)
  • Improved Upper Bounds for Finding Tarski Fixed Points (arXiv, EC)
  • Tight Incentive Analysis on Sybil Attacks to Market Equilibrium of Resource Exchange over General Networks (SSRN, EC)
  • 2021

  • On Tightness of the Tsaknakis-Spirakis Algorithm for Approximate Nash Equilibrium (arXiv, SAGT, I&C)
  • 2020

  • Limiting the Deviation Incentives in Resource Sharing Networks (AAMAS, APJOR)
  • Tightening up the incentive ratio for resource sharing over the rings (IPDPS)
  • Preprints

  • Learning to Manipulate a Commitment Optimizer (arXiv)
  • Academic Experience

  • McGill University (Summer 2023), hosted by Prof. Robert Robere
  • Simons Institute, UC Berkerley (Spring 2023), Meta-Complexity program
  • Peking University (Summer 2022), hosted by Prof. Xiaotie Deng
  • Professional Service

  • Conference Review
  • Journal Review
  • Contact

    Last updated: 9 Feb, 2024