Xinkai Shu
Max Planck Institute for Informatics, Saarbrücken, Germany.
I am currently a postdoctoral researcher at the Max Planck Institute for Informatics, hosted by Danupon Nanongkai.
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 lies broadly in theoretical computer science. I focus mainly on online algorithms beyond worst-case analysis, including algorithms with predictions and stochastic input models. In particular, I study online matching, selection, and resource allocation problems. I also work on approximation algorithms and fundamental graph algorithms.
Email: xshu [at] mpi [hyphen] inf [dot] mpg [dot] de
Office: Room 316, Max Planck Institute for Informatics
News
| 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. |
| Apr 2025 | Our paper The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization (joint work with Zhiyi Huang, Chui Shan Lee, and Zhaozi Wang) was accepted to ICALP 2025. |
| Feb 2025 | Our paper Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (joint work with Ran Duan, Jiayi Mao, Xiao Mao, and Longhui Yin) was accepted to STOC 2025 and received the Best Paper Award. |
