Zhihao Tang

唐志皓


About Me

I am an assistant professor at ITCSShanghai University of Finance and Economics. I have obtained my PhD degree in Feb 2019 under the supervision of Dr. Hubert Chan at the University of Hong Kong. Before that, I received my BSc in Mathematics and BA in Economics from Peking University in 2014.
I am broadly interested in theoretical computer science, particularly in algorithms under uncertainty. More specifically, I work on 
online algorithms and algorithmic game theory. Check my publications for more details.


Contact


Office:
Room 605, School of Information Management and Engineering
Shanghai University of Finance and Economics


Email:
tang.zhihao [at] mail.shufe.edu.cn
gavintang3 [at] gmail.com



Publication



2021

Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang

COLT 2021: 34th Annual Conference on Learning Theory [arxiv]

Online Selection Problems Against Constrained Adversary

Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang

ICML 2021: 38th International Conference on Machine Learning


Random Order Vertex Arrival Contention Resolution Schemes For Matching, With Applications

Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang

ICALP2021: 48th International Colloquium on Automata, Languages, and Programming


Online Stochastic Matching with Edge Arrivals

Nick Gravin, Zhihao Gavin Tang, and Kangning Wang

ICALP 2021: 48th International Colloquium on Automata, Languages, and Programming [arxiv]


2020

Tight Revenue Gaps among Simple Mechanisms

Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao

SICOMP 2020: SIAM Journal on Computing, 49(5), 2020 [journal] [arxiv]
Preliminary version appeared in
 SODA 2019


Fully Online Matching

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

JACM 2020: Journal of the ACM, 17(3), 2020 [journal]
Preliminary version appeared in 
STOC 2018


Re-Revisiting Learning on Hypergraphs: Confidence Interval, Subgradient Method, and Extension to Multiclass

Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and T.-H. Hubert Chan (by contribution)

TKDE 2020: IEEE Transaction on Knowledge and Data Engineering, 32(3), 2020 [journal]
Preliminary version appeared in
 ICML 2017


Fully Online Matching II: Beating Ranking and Water-filling

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

FOCS 2020: 61st Annual IEEE Symposium on Foundations of Computer Science [arxiv]


Online Stochasitc Max-Weight Matching: prophet inequality for vertex and edge arrival models

Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang

EC 2020: 21st ACM Conference on Economics and Computation [arxiv]


Towards a Better Understanding of Randomized Greedy Matching

Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

STOC 2020: 52nd Annual ACM SIGACT Symposium on Theory of Computing [arxiv]


2019

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

TALG 2019: ACM Transactions on Algorithms, 15(3), 2019 [arxiv]
Preliminary version appeared in 
ICALP 2018

Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian

T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, and Chenzi Zhang

TCS 2019: Theoretical Computer Science, 784:46-64, 2019 [arxiv]

Tight Approximation Ratio of Anonymous Pricing

Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao

STOC 2019: 51st Annual ACM SIGACT Symposium on Theory of Computing [arxiv]

Correlation-Robust Analysis of Single Item Auction

Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang

SODA 2019: 30th Annual ACM-SIAM Symposium on Discrete Algorithms [conference]

Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model

Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang

SODA 2019: 30th Annual ACM-SIAM Symposium on Discrete Algorithms [arxiv]

Tight Revenue Gaps among Simple Mechanisms

Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao

SODA 2019: 30th Annual ACM-SIAM Symposium on Discrete Algorithms [arxiv]


2018

Spectral Properties of Hypergraph Laplacian and Approximation Algorithms

T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang

JACM 2019: Journal of the ACM, 65(3), 2018 [arxiv]

Online Submodular Maximization with Free Disposal

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

TALG 2018: ACM Transactions on Algorithms (TALG), 14(4), 2018 [journal] [arxiv]
Preliminary version appeared in 
SODA 2017

On (1,ε)-Restricted Max-Min Fair Allocation Problem

T.-H. Hubert Chan, Zhihao Gavin Tang, and Xiaowei Wu

Algorithmica (Invited Paper), 80(7), 2018 [arxiv]
Preliminary version appeared in 
ISAAC 2016

Online Makespan Minimization: The Power of Restart

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

APPROX 2018: 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems [arxiv]

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming [arxiv]

How to Match when All Vertices Arrive Online

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu

STOC 2018: 50th Annual ACM SIGACT Symposium on Theory of Computing [arxiv]

The Value of Information Concealment

Hu Fu, Christopher Liaw, Pinyan Lu, and Zhihao Gavin Tang

SODA 2018: 29th Annual ACM-SIAM Symposium on Discrete Algorithms [arxiv]


2017

Online Submodular Maximization Problem with Vector Packing Constraint

T.-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, and Xiaowei Wu

ESA 2017: 25th Annual European Symposium on Algorithms [arxiv]

Re-revisiting Learning on Hypergraphs: Confidence Interval and Subgradient Method

Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and T.-H. Hubert Chan (by contribution)

ICML 2017: 34th International Conference on Machine Learning [conference]

Graph Edge Partitioning via Neighborhood Heuristic

Chenzi Zhang, Fan Wei, Qin Liu, Zhihao Gavin Tang, and Zhenguo Li (by contribution)

KDD 2017: 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining [conference]

Online Submodular Maximization with Free Disposal: Randomization Beats 1/4 for Partition Matroids

T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, and Zhihao Gavin Tang

SODA 2017: 28th Annual ACM-SIAM Symposium on Discrete Algorithms [arxiv]


2016

On (1,ε)-Restricted Max-Min Fair Allocation Problem

T.-H. Hubert Chan, Zhihao Gavin Tang, and Xiaowei Wu

ISAAC 2016: 27th International Symposium on Algorithms and Computation [arxiv]


2015

Cheeger Inequalities for General Edge-Weighted Directed Graphs

T.-H. Hubert Chan, Zhihao Gavin Tang, and Chenzi Zhang

COCOON 2015: 21st International Computing and Combinatorics Conference (COCOON 2015) [conference]