Xinkai Shu

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

avatar_small.jpg

I am currently a postdoctoral researcher at the Max Planck Institute for Informatics, hosted by Danupon Nanongkai. I will be leaving the institute by July 29th, and I want to thank everyone here for a truly wonderful experience!

I obtained my PhD degree in Computer Science from The University of Hong Kong, where I was very fortunate to be supervised by Zhiyi Huang. Before that, I obtained my bachelor’s degree from Yao Class, Tsinghua University.

My research mainly focuses on online algorithms beyond worst-case analysis, including algorithms with predictions and stochastic input models. Much of my work studies matching, selection, and resource allocation problems arising in online decision making. I also work on fast algorithms for fundamental graph problems, especially shortest paths.

Email: varepsilonshu [at] gmail [dot] com (Primary), xshu [at] mpi [hyphen] inf [dot] mpg [dot] de (Expire soon) Office: Room 316, Max Planck Institute for Informatics

Selected Publications

  1. 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. Invited to the Journal of ACM
    arXiv DOI 44 Google Scholar citations
  2. 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
    arXiv DOI 21 Google Scholar citations
  3. The Power of Multiple Choices in Online Stochastic Matching
    Zhiyi Huang, Xinkai Shu, and Shuyi Yan
    In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, Jun 2022
    arXiv DOI 57 Google Scholar citations
  4. 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
    arXiv DOI 68 Google Scholar citations

News

Jul 2026 I will be leaving the Max Planck Institute for Informatics by July 29th. Thank you all for the wonderful experience!
Apr 2026 Our paper A Faster Directed Single-Source Shortest Path Algorithm (joint work with Ran Duan, Xiao Mao, and Longhui Yin) was accepted to ICALP 2026.
Jul 2025 I gave a talk on Breaking the Sorting Barrier for Directed Single-Source Shortest Paths at IJTCS-FAW 2025.