Yaonan Jin (金耀楠)

I am a full-time researcher at the Huawei Theoretical Computer Science Lab led by Prof. Pinyan Lu. Before joining Huawei, I obtained my PhD from Columbia University in 2023, where I was advised by Prof. Xi Chen and Prof. Rocco Servedio. Prior to that, I obtained my MPhil from Hong Kong University of Science and Technology, where I was advised by Prof. Qi Qi, and my BEng from Shanghai Jiao Tong University.

Contact

• Email: jinyaonan@huawei.com

Curriculum Vitae

Research Interests

• Theoretical Computer Science
• Algorithmic Economics
• Randomness in Computation
• Sublinear Algorithms

Publications

Surveys

• Settling the Efficiency of 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
  Yaonan Jin and Pinyan Lu
  Submitted to SIAM Journal on Computing
• Learning Reserve Prices in Second Price Auctions [arXiv]
  Yaonan Jin, Pinyan Lu, and Tao Xiao
  Submitted to ACM Transactions on Economics and Computation
• 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
• 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 Multi-Unit 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): 1-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

• Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
  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

• Efficient Clustering on Sparse Graphs via Super-effective Local Search
  Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, and Pinyan Lu
• Beyond Regularity: Simple versus Optimal Mechanisms, Revisited [arXiv]
  Yiding Feng and 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