Publications   Highlights of My Research Journey   Teaching   Favourite Quotes, Articles and Hobbies   My Google Scholar   My DBLP   CV (PDF)

Yun Kuen (Marco) CHEUNG

Email:   (replace # by an appropriate alphabet)
Office: Bedford 1-14

Introducing Myself

I am a lecturer in Computer Science, at Royal Holloway University of London (RHUL), UK. I got my PhD in Computer Science at Courant Institute of Mathematical Sciences, New York University, advised by Prof. Richard Cole. I have held postdoctoral positions at University of Vienna, Max-Planck-Institut (MPI) für Informatik and Singapore University of Technology and Design (SUTD), mentored/hosted by Prof. Monika Henzinger, Direktor Kurt Mehlhorn and Dr. Georgios Piliouras respectively. Before PhD, I got my MPhil in Mathematics and BSc in Mathematics & Physics at Hong Kong University of Science and Technology (HKUST); my MPhil advisor is Prof. Mordecai J. Golin. (Yes, I have lived in Hong Kong, New York, Vienna, Singapore, and now near London!)

I was born in Hong Kong before 1997, a time before the abyss.

Research Interests

I am a theoretical computer scientist working in the areas of Computational Economics, Algorithmic Game Theory, Dynamical-systemic Aspects of Machine Learning and Discrete Mathematics. More specifically, I am currently focusing on the following topics: The first two topics are highly inter-connected with the broad areas of Dynamical Systems, Chaos Theory, Optimization and Parallel Computing. Please read a short essay about highlights of my research journey.


This contains rolling updates of my research activities. When a paper is accepted, I write a short paragraph to describe the motivation, the background and our main contributions.

Publications (in reverse chronological order)

Manuscript / Ongoing Work

[M1] Allocation of Mining Resources in the Blockchain Economy
          with Stefanos Leonardos, Shyam Sridhar and Georgios Piliouras. Working Paper, appeared in WINE 2020 Workshop on Blockchain.

Peer-Reviewed Publications

[19] Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
          with Yixin Tao. To appear in ICLR 2021.   [arxiv]

[18] Fully Asynchronous Stochastic Coordinate Descent: A Tight Lower Bound on the Parallelism Achieving Linear Speedup
          with Richard Cole and Yixin Tao. Accepted to Mathematical Programming (Series A) in September 2020.   [official]    [arxiv]

[17] Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism
          with Richard Cole and Yixin Tao. In SIAM Journal on Optimization (SIOPT) Volume 31 Issue 1, February 2021.  [official]  [arxiv]

[16] Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
         with Georgios Piliouras. NeurIPS 2020.   [arxiv]

[15] Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
         with Richard Cole and Nikhil R. Devanur. STOC 2013.   [official for STOC]
         Full journal version in Games and Economic Behavior Volume 123, September 2020 (Special Issue for STOC/FOCS/SODA 2013).   [official for GEB]

[14] Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
         with Georgios Piliouras. COLT 2019.   [official]    [arxiv]

[13] Tracing Equilibrium in Dynamic Markets via Distributed Adaptation
         with Martin Hoefer and Paresh Nakhe. AAMAS 2019.   [official]   [arxiv]

[12] Steiner Point Removal -- Distant Terminals Don't (Really) Bother
         SODA 2018.   [official]   [arxiv]

[11] Dynamics of Distributed Updating in Fisher Markets
         with Richard Cole and Yixin Tao. ACM EC 2018.   [official]   [arxiv]

[10] Spanning Tree Congestion and Computation of Generalized Győri-Lovász Partition
         with L. Sunil Chandran and Davis Issac. ICALP 2018.   [official]   [arxiv]

[09] Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games
         NeurIPS 2018.   [official]

[08] Amortized Analysis of Asynchronous Price Dynamics
         with Richard Cole. ESA 2018.   [official]   [arxiv]

[07] On Fair Division of Indivisible Items
         with Bhaskar Ray Chaudhury, Jugal Garg, Naveen Garg, Martin Hoefer and Kurt Mehlhorn. FSTTCS 2018.   [official]   [arxiv]

[06] Graph Minors for Preserving Terminal Distances Approximately -- Lower and Upper Bounds
         with Gramoz Goranci and Monika Henzinger. ICALP 2016.   [official]   [arxiv]

[05] Better Strategyproof Mechanisms without Payments or Prior -- An Analytic Approach
         IJCAI 2016.   [official]   [arxiv]

[04] Combinatorial Auctions with Conflict-Based Externalities
         with Monika Henzinger, Martin Hoefer and Martin Starnberger. WINE 2015.   [official]   [arxiv]

[03] Tatonnement in Ongoing Markets of Complementary Goods
         with Richard Cole and Ashish Rastogi. ACM EC 2012.   [official]   [arxiv]

[02] Analyzing a Weighted Digital Sum Variant
         with Mordecai Golin. AofA 2010.   [official]   [arxiv for [01] and [02]]

[01] Multidimensional Divide-and-Conquer and Weighted Digital Sums
         with Philippe Flajolet, Mordecai Golin, C.Y. James Lee. ANALCO 2009.   [official]   [arxiv for [01] and [02]]

Theses and Book Chapter

Book Chapter: Divide-and-Conquer Recurrences and the Mellin-Perron Formula
         with Mordecai Golin. To appear as a chapter in Collected Works of Philippe Flajolet.

PhD Thesis (2014): Analyzing Tatonnement Dynamics in Economics Markets

MPhil Thesis (2009): Analysis of Weighted Digital Sums by Mellin Transform