Education and Recent Positions   Publications   Highlights of My Research Journey   Teaching   Favourite Quotes, Articles and Hobbies   My DBLP

Yun Kuen (Marco) CHEUNG

Introducing Myself

I am a theoretical computer scientist working in the areas of Algorithmic Game Theory and Combinatorics. More specifically, I am currently focusing on the following topics: The first two topics are highly inter-connected with the broad areas of Optimization and Dynamical Systems. I provide two pictorial illuminations of these connections, and a short essay about highlights of my research journey. (Click the pics below for magnified version and legend to the graphs.)


Email:   (replace # by alphabet 'c')

Education and Recent Positions

Sept 2018 --      
Research Fellow at Engineering Systems and Design Pillar of Singapore University of Technology and Design.
Group leader: Georgios Piliouras.
Sept 2016 --
Aug 2018:
Postdoctoral Fellow at Department 1: Algorithms and Complexity of Max-Planck-Institut (MPI) für Informatik.
Department Director: Kurt Mehlhorn.
Sept 2014 --
July 2016:
Postdoctoral Researcher at the research group Theory and Applications of Algorithms
in Faculty of Computer Science, University of Vienna. Group leader: Monika Henzinger.
Sept 2009 --
Aug 2014:
PhD in Computer Science, Courant Institute of Mathematical Sciences, New York University.
Advisor: Richard Cole.
Sept 2007 --
Aug 2009:
MPhil in Mathematics, The Hong Kong University of Science and Technology.
Advisor: Mordecai J. Golin.
Sept 2004 --
Aug 2007:
BSc in Mathematics and Physics, The Hong Kong University of Science and Technology.
Minor in Information Technology (Computer Science). Academic Achievement Medallist.

Publications (in reverse chronological order)

Manuscript / Ongoing Work

[M2] Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup
          with Richard Cole and Yixin Tao. Submitted. Paper will be available here soon.

[M1] Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism
          with Richard Cole and Yixin Tao. Submitted.   [arxiv]

Peer-Reviewed Publications

[15] Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
         with Georgios Piliouras. COLT 2019. Paper will be available here soon.

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

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

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

[11] Amortized Analysis of Asynchronous Price Dynamics
         with Richard Cole. ESA 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] Dynamics of Distributed Updating in Fisher Markets
         with Richard Cole and Yixin Tao. ACM EC 2018.   [official]   [arxiv]

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

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

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

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

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

[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
         New World Mathematics Silver Award for Master Thesis in 2010.

Imprint | Data Protection