Publications

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

2025

  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
    arXiv DOI
  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
    arXiv DOI

2024

  1. Online Matching Meets Sampling Without Replacement
    Zhiyi Huang, Chui Shan Lee, Jianqiao Lu, and Xinkai Shu
    In Proceedings of the 20th Conference on Web and Internet Economics (WINE 2024), Edinburgh, United Kingdom, Dec 2024
    arXiv

2023

  1. Online Nash Welfare Maximization Without Predictions
    Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei
    In Proceedings of the 19th Conference on Web and Internet Economics (WINE 2023), Shanghai, China, Dec 2023
    arXiv DOI
  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

2022

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

2021

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