Speaker: Zhiyi Huang University of Hong Kong
Time: 2023-09-25 15:00-2023-09-25 16:00
Venue: FIT 1-222

Abstract:

We initiate the study of Online Correlated Selection (OCS). Consider a set of ground elements and a sequence of pairs of elements that arrive one at a time. Upon the arrival of each pair, the algorithm selects one of the two elements. For example, we can select with a fresh random bit every time. Then, after an element appears in k pairs, it will be selected at least once with a probability of 1-2^{-k}. Can we do better?

This talk will survey what we know and do not know about OCS. As applications, researchers have designed new algorithms based on OCS for many online matching problems. Notably, these online matching algorithms broke the long-standing 0.5 barrier in the edge-weighted online matching problem (also known as Display Ads) and AdWords, and the 1-1/e barrier in non-IID online stochastic matching.

Short Bio:

Zhiyi is an associate professor of Computer Science at the University of Hong Kong. He works broadly on Theoretical Computer Science and Algorithmic Game Theory, with a focus on optimization and decision-making under uncertainty. Before joining HKU, Zhiyi was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. He obtained his Ph.D. from the University of Pennsylvania under Sampath Kannan and Aaron Roth in 2013. During grad school, Zhiyi interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012. Before that he got a bachelor degree from the first "Yao Class" under Andrew Yao at Tsinghua University in 2008. Zhiyi was the recipient of the Best Paper Awards of FOCS 2020 and SPAA 2015, an Excellent Young Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong Kong, and a Morris and Dorothy Rubinoff Dissertation Award.