Post Doc Research Fellow


Pillar / Cluster: Engineering Systems and Design


Yun Kuen (Marco) works on various topics under Theoretical Computer Science, Algorithm Design and Analysis, and Discrete Mathematics. One of his foci is the computational and dynamical aspects of game theory and economics. Perhaps surprisingly to some, this has led him and his coauthors to investigate into asynchronous algorithms in optimization, for which they developed an amortized analysis approach towards theoretical understanding of such algorithms. His another foci is on graph partitioning and sparsification.

Marco was born and grew up in Hong Kong. During high school, he developed a strong interest in Mathematics via Mathematical Olympiad. He was a team member of Hong Kong in International Mathematical Olympiad (IMO) 2004. After five years of college life in Hong Kong University of Science and Technology (HKUST), he pursued PhD study in New York University (NYU), in which he was fortunate to be advised by Prof. Richard Cole. He then worked in University of Vienna and Max Planck Institute of Informatics (MPII) for a total of four years.


  • PhD in Computer Science, New York University (NYU), 2014
  • MPhil in Mathematics, Hong Kong University of Science and Technology (HKUST), 2009
  • BSc in Mathematics and Physics, Hong Kong University of Science and Technology (HKUST), 2007

Research Interest

Computational and dynamical aspects of game theory and economics, asynchronous optimization, graph partitioning and sparsification

Selected Publications

A) On Game/Market Dynamics and Asynchronous Dynamics/Optimization

  • Yun Kuen Cheung, Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games, NIPS 2018 (to appear)
  • Yun Kuen Cheung and Richard Cole, Amortized Analysis of Asynchronous Price Dynamics, ESA 2018
  • Yun Kuen Cheung, Richard Cole and Yixin Tao, Dynamics of Distributed Updating in Fisher Markets, EC 2018
  • Yun Kuen Cheung, Richard Cole and Nikhil Devanur, Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue, STOC 2013

B) On Graph Partitioning and Sparsification

  • Yun Kuen Cheung, Steiner Point Removal — Distant Terminals Don’t (Really) Bother, SODA 2018
  • L. Sunil Chandran, Yun Kuen Cheung and Davis Issac, Spanning Tree Congestion and Computation of Generalized Gyori-Lovasz Partition, ICALP 2018
  • Yun Kuen Cheung, Gramoz Goranci and Monika Henzinger, Graph Minors for Preserving Terminal Distances Approximately — Lower and Upper Bounds, ICALP 2016