Yuhao Li (李毓浩)

Yuhao Li

I am a fourth-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 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.

I am broadly interested in theoretical computer science and discrete mathematics, including complexity theory (TFNP, proof complexity, communication complexity), logic, automata theory, games, and combinatorics.







Selected Publications

2025

  • Metamathematics of Resolution Lower Bounds: A TFNP Perspective (ECCC)
  • Relative-error Monotonicity Testing (arXiv)

    • 2024

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

    • 2023

  • Reducing Tarski to Unique Tarski (in the Black-box Model) (ECCC)

    • 2022

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

    • I also occasionally chat with my friends about problems arising in Blockchain. Authors of papers below are listed in non-alphabetical order, with * denoting first author(s).

    Blockchain and Cryptocurrency

  • Computation of Optimal MEV in Decentralized Finance
  • MEV Makes Everyone Happy under Greedy Sequencing Rule (arXiv)
  • Insightful Mining Equilibria (arXiv)

    • Preprints

  • Learning to Manipulate a Commitment Optimizer (arXiv)

    • Academic Experience

  • Simons Institute, UC Berkerley (Summer 2024), Sublinear Algorithm (and Theoretical Foundations of Computer Systems)
  • McGill University (Summer 2023), hosted by Prof. Robert Robere
  • Simons Institute, UC Berkerley (Spring 2023), Meta-Complexity
  • Peking University (Summer 2022), hosted by Prof. Xiaotie Deng

    • Professional Service

  • Conference Review
  • Journal Review

    • Contact

    Last updated: Nov 13, 2024