Publications

Authors are listed in alphabetical order following the traditions of theoretical computer science, unless stated otherwise.

2026

  1. A Faster Directed Single-Source Shortest Path Algorithm
    Ran Duan, Xiao Mao, Xinkai Shu, and Longhui Yin
    53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2026)
    arXiv conference scholar 3

2025

  1. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization
    Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang
    52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2025)
    arXiv conference scholar 9
  2. 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

2024

  1. Online Matching Meets Sampling Without Replacement
    Zhiyi Huang, Chui Shan Lee, Jianqiao Lu, and Xinkai Shu
    20th Conference on Web and Internet Economics (WINE 2024)
    arXiv conference scholar 2

2023

  1. Online Nash Welfare Maximization Without Predictions
    Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei
    19th Conference on Web and Internet Economics (WINE 2023)
    arXiv conference scholar 13
  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

2022

  1. 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

2021

  1. 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