Xinkai Shu

Max Planck Institute for Informatics, Saarbrücken, Germany.

avatar_small.jpg

I’m currently a postdoctoral researcher at Max Planck Institute for Informatics. I obtained my PhD degree in Computer Science at The University of Hong Kong, where I was very fortunate to be supervised by Prof. Zhiyi Huang. Before that I obtained my bachelor’s degree from Yao Class, Tsinghua University, instructed by Prof. Ran Duan. I’m currently interested in online algorithms, algorithmic game theory and fundamental graph algorithms.




Room 316, Max Planck Institute for Informatics
Campus E 1 4, Saarland Informatics Campus
66123 Saarbrücken, Germany
xshu@mpi-inf.mpg.de

News

Apr 14, 2025 Our paper The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization (joint work with Zhiyi Huang, Chui Shan Lee & Zhaozi Wang) has been accepted to ICALP 2025.
Feb 24, 2025 Our paper Breaking the Sorting Barrier for Directed Single-Source Shortest Pathsg (joint work with Ran Duan, Jiayi Mao, Xiao Mao & Longhui Yin) has been accepted to STOC 2025, and received the Best Paper Award.
Sep 16, 2024 Our paper Online Matching Meets Sampling Without Replacement (joint work with Zhiyi Huang, Chui Shan Lee & Jianqiao Lu) has been accepted to WINE 2024.
Jul 24, 2024 I have officially obtained my PhD degree at the University of Hong Kong!
Sep 08, 2023 Our paper Online Nash Welfare Maximization Without Predictions (joint work with Zhiyi Huang, Minming Li & Tianze Wei) has been accepted to WINE 2023.

Selected Publications

  1. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization
    Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang
    In Proceedings of the 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2025), Aarhus, Denmark, Jul 2025
  2. Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
    Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin
    In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), Prague, Czech Republic, Jun 2025
    Best Paper Award
  3. A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
    Ran Duan, Jiayi Mao, Xinkai Shu, and Longhui Yin
    In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, USA, Nov 2023
  4. The Power of Multiple Choices in Online Stochastic Matching
    Zhiyi HuangXinkai Shu, and Shuyi Yan
    In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, Jun 2022
  5. Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
    Zhiyi Huang, and Xinkai Shu
    In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021), Rome, Italy (virtually), Jun 2021