17 citations · 95 across the 34 of their papers we have counts for
3 papers · 1 filter
Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang +1
This paper explores a theory of generalization for learning problems on product distributions, complementing the existing learning theories in the sense that it does not rely on an…
Online Stochastic Matching with Edge Arrivals
Nick Gravin, Zhihao Gavin Tang, Kangning Wang
Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by [Gamlath et al. FOCS 2019], who showed that no online…
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
There has been a long history for studying randomized greedy matching algorithms since the work by Dyer and Frieze~(RSA 1991). We follow this trend and consider the problem formula…