Yaonan Jin (金耀楠)

I am an Assistant Professor in the Department of Computer Science and Engineering at the Hong Kong University of Science and Technology. Before joining HKUST, I was a researcher at Huawei's Taylor Lab (formerly the Theoretical Computer Science Lab), working with Pinyan Lu. I obtained my PhD from Columbia University in 2023, where I was advised by Xi Chen and Rocco Servedio. Prior to that, I obtained my MPhil from Hong Kong University of Science and Technology, where I was advised by Qi Qi, and my BEng from Shanghai Jiao Tong University.

Contact

• Email: jinyaonan@ust.hk

Curriculum Vitae

Research Interests

• Theoretical Computer Science
• Economics and Computation
• Online Algorithms
• Combinatorial Optimization

Publications

Surveys

• Settling the Efficiency of the First-Price Auction [PDF]
  Yaonan Jin and Pinyan Lu
  ACM SIGecom Exchanges, 20(2): 69-74, 2022
• Tight Revenue Gaps among Simple and Optimal Mechanisms [PDF]
  Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Tang, and Tao Xiao
  ACM SIGecom Exchanges, 17(2): 54-61, 2019

Journal Papers

• Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer [arXiv]
  Yaonan Jin and Pinyan Lu
  To appear in SIAM Journal on Computing
• First Price Auction is $1 - 1 / e^{2}$ Efficient [arXiv]
  Yaonan Jin and Pinyan Lu
  Journal of the ACM, 70(5): 36:1-36:86, 2023
• Fourier Growth of Structured $\mathbb{F}_2$-Polynomials and Applications [arXiv] [ECCC]
  Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, and Emanuele Viola
  (Invited Paper) To appear in Theory of Computing
• Tight Revenue Gaps among Multiunit Mechanisms [arXiv]
  Yaonan Jin, Shunhua Jiang, Pinyan Lu, and Hengjie Zhang
  SIAM Journal on Computing, 51(5): 1535-1579, 2022
• Optimal Budget-Feasible Mechanisms for Additive Valuations [arXiv]
  Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang
  ACM Transactions on Economics and Computation, 8(4): 21:1-21:15, 2020
• Tight Revenue Gaps among Simple Mechanisms [arXiv]
  Yaonan Jin, Pinyan Lu, Zhihao Tang, and Tao Xiao
  SIAM Journal on Computing, 49(5): 927-958, 2020

Conference Papers

• The Price of Anarchy for Selfish Load Balancing under Correlated Priors
  Xihan Deng, Yaonan Jin, Wenqian Wang, and Yuhao Zhang
  International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom (IJTCS-FAW 2026)
• The Price of Anarchy for Selfish Load Balancing
  Xihan Deng, Yaonan Jin, Wenqian Wang, and Yuhao Zhang
  67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)
• Fully Dynamic Euclidean $k$-Means [arXiv]
  Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Shaofeng H.-C. Jiang, Yaonan Jin, and Jianing Lou
  67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)
• Anonymous Pricing in Large Markets [arXiv]
  Yaonan Jin and Yingkai Li
  27th ACM Conference on Economics and Computation (EC 2026)
• Tight Regret Bounds for Fixed-Price Bilateral Trade [arXiv]
  Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang
  53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)
• The Query Complexity of Uniform Pricing [arXiv]
  Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang
  35th ACM Web Conference (WWW 2026)
• Local Search for Clustering in Almost-linear Time [arXiv]
  Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, and Pinyan Lu
  37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)
• Beyond Regularity: Simple versus Optimal Mechanisms, Revisited [arXiv]
  Yiding Feng and Yaonan Jin
  66th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2025)
• Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer [arXiv]
  Yaonan Jin and Pinyan Lu
  65th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2024)
• Subset Sum in Time $2^{n/2} / \mathrm{poly}(n)$ [arXiv]
  Xi Chen, Yaonan Jin, Tim Randolph, and Rocco Servedio
  27th International Workshop on Randomization and Computation (RANDOM 2023)
• Learning Reserve Prices in Second Price Auctions [arXiv]
  Yaonan Jin, Pinyan Lu, and Tao Xiao
  14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
• Super-Resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity [arXiv]
  Yaonan Jin, Daogao Liu, and Zhao Song
  34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
• The Price of Stability for First Price Auction [arXiv]
  Yaonan Jin and Pinyan Lu
  34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
• First Price Auction is $1 - 1 / e^{2}$ Efficient [arXiv]
  Yaonan Jin and Pinyan Lu
  63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022)
• Average-Case Subset Balancing Problems [arXiv]
  Xi Chen, Yaonan Jin, Tim Randolph, and Rocco Servedio
  33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
• Fourier Growth of Structured $\mathbb{F}_2$-Polynomials and Applications [arXiv] [ECCC]
  Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, and Emanuele Viola
  25th International Workshop on Randomization and Computation (RANDOM 2021)
• Tight Revenue Gaps among Multi-Unit Mechanisms [arXiv]
  Yaonan Jin, Shunhua Jiang, Pinyan Lu, and Hengjie Zhang
  22nd ACM Conference on Economics and Computation (EC 2021)
• On the Approximability of Simple Mechanisms for MHR Distributions [PDF]
  Yaonan Jin, Weian Li, and Qi Qi
  15th Conference on Web and Internet Economics (WINE 2019)
• Optimal Budget-Feasible Mechanisms for Additive Valuations [arXiv]
  Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang
  20th ACM Conference on Economics and Computation (EC 2019)
• Tight Approximation Ratio of Anonymous Pricing [arXiv]
  Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Tang, and Tao Xiao
  51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019)
• Tight Revenue Gaps among Simple Mechanisms [arXiv]
  Yaonan Jin, Pinyan Lu, Zhihao Tang, and Tao Xiao
  30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

Manuscripts

• Round-Efficient Fully-Scalable MPC Algorithms for $k$-Means [arXiv]
  Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, and Weicheng Wang
• Tight Regret Bounds for Bilateral Trade under Semi Feedback [arXiv]
  Yaonan Jin
• On Asymptotically Tight Tail Bounds for Sums of Geometric and Exponential Random Variables [arXiv]
  Yaonan Jin, Yingkai Li, Yining Wang, and Yuan Zhou