Education and Recent Positions
Favourite Quotes, Articles and Hobbies
A→B: B is a sub-category or A. (Not necessarily transitive. :-p)
Blue Color: Broad research areas where my research relates to. I am familiar with the background knowledge and development of these areas.
Red Color: Research subfields which I am currently focusing on.
Green Color: Research subfields on which I have conducted research. I am very happy to hear about interesting problems in these areas.
Purple Color: Some topics / keywords in my research.
Highlights of My Research Journey
One of my research foci is natural algorithms in economics, or more concretely, (learning) dynamics in games and markets. This topic has rich inter-connection with the fields Optimization, Dynamical System and Distributed Computing. Indeed, the study of tatonnement price dynamics in markets (see my EC'2012, STOC'2013 and ESA'2018 papers) has brought me, my PhD advisor Richard Cole and my close collaborator Yixin Tao to one of our key research projects on asynchronous optimization method and dynamics. The key question addressed in this project is:
many well-known optimization methods are readily parallelizable in uncoordinated/asynchronous manner,
Recently, Richard, Yixin and I also studied another market dynamic called proportional response dynamic (PRD), which has been naturally motivated by peer-to-peer sharing network.
Along the way, we developed brand new methods and analyses on convex and min-max optimization. (EC'2018)
but as common wisdom suggests, overdosing parallelism can lead to a mess;
so, what is the limit of admissible parallelism?
In collaboration with my current mentor Georgios Piliouras (COLT'2019), we present rigorous mathematical proofs to show that
the canonical learning algorithm Multiplicative Weights Updates (MWU) in zero-sum games is Lyapunov chaotic!
Zero-sum games are generally viewed as the exemplar symbol of stability and predictability in game theory, due to John von Neumann's Linear Program duality. In stark contrast, by proving MWU is Lyapunov chaotic in zero-sum games, we provide one of the strongest possible indications that zero-sum game is unpredictable in the long run from a dynamic perspective. This generalizes the non-equilibration analysis of MWU in zero-sum game in my NeurIPS'2018 paper. The key tool "volume analysis" used for demonstrating Lyapunov chaos is novel and generally applicable in the context of game dynamics: we have demonstrated its power applicable beyond MWU and zero-sum games, and we believe it has a potential to lead to a new paradigm of understanding of game dynamics.
During the training process towards becoming an International Mathematical Olympiad (IMO) team member of Hong Kong in 2004, and while I was completing my BSc and MPhil degrees in my birthplace Hong Kong, I developed a strong interest in combinatorics / discrete mathematics. During my first postdoc (2014-2016) mentored by Monika Henzinger, I had a chance to pick up this interest and have conducted several research projects on combinatorics problems about graphs. Here are some highlights:
I have also worked on several other topics, including fair allocation of indivisible items, mechanism/auction design, analytic combinatorics and its applications in algorithm analysis.
Imprint | Data Protection
- I presented an analysis that leads to O(log^2 k) distortion guarantee on Steiner Point Removal (SPR) problem (SODA'2018); this lays down a foundation for the latter improvement to O(log k) by Arnold Filtser.
- with L. Sunil Chandran and Davis Issac (ICALP'2018), we presented tight bounds on Spanning Tree Congestion problem, and along the way we devised algorithms for (approximately) computing Generalized Győri-Lovász partition of well-connected graphs: informally, it is a partition of the vertices into a fixed number of connected components with approximately equal sums of weights;
- with Monika and Gramoz Goranci (ICALP'2016), we present some interesting results on a relaxation of the SPR problem called Distance Approximating Minor (DAM).