Xinkai Shu

I am a tenure-track professor at the University of Science and Technology of China (USTC). Previously, I was a postdoctoral researcher at the Max Planck Institute for Informatics, hosted by Danupon Nanongkai. Before that, I received my PhD in Computer Science from The University of Hong Kong, where I was very fortunate to be supervised by Zhiyi Huang. I completed my undergraduate studies in the Yao Class at 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 concerns matching, selection, and resource allocation problems arising in online decision making. I also study fast algorithms for shortest paths.

Email: shuxinkai [at] ustc [dot] edu [dot] cn Office: Room C-301, Block C, Academic Building No. 1
High-tech Campus, University of Science and Technology of China
No. 100 Fuxing Road
Hefei, Anhui 230088, China

Selected Publications

  1. Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
    Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin
    57th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2025)
    Best Paper Award. Accepted to the Journal of the ACM
    arXiv journal conference scholar 69
  2. A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
    Ran Duan, Jiayi Mao, Xinkai Shu, and Longhui Yin
    64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023)
    arXiv conference scholar 23
  3. The Power of Multiple Choices in Online Stochastic Matching
    Zhiyi Huang, Xinkai Shu, and Shuyi Yan
    54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)
    arXiv conference scholar 62
  4. Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
    Zhiyi Huang and Xinkai Shu
    53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
    arXiv conference scholar 73

News

Aug 2026 I joined the University of Science and Technology of China as a tenure-track professor.
Jul 2026 I left the Max Planck Institute for Informatics on July 29. Many thanks to everyone there for a 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.