publications

publications by categories in reversed chronological order. Authors are listed in alphabetical order following the traditions of theoretical computer science, unless stated otherwise.

2025

  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, Czechia, Jun 2025
    Best Paper Award
    DOI

2023

  1. 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, CA, USA, Nov 2023
    DOI

2022

  1. Optimal vertex connectivity oracles
    Seth Pettie, Thatchaphol Saranurak, and Longhui Yin
    In Proceedings of the 54th Annual ACM Symposium on Theory of Computing, STOC 2022, Rome, Italy, Jun 2022
    DOI

2021

  1. The Structure of Minimum Vertex Cuts
    Seth Pettie and Longhui Yin
    In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), Jul 2021
    DOI
  2. Non-Mergeable Sketching for Cardinality Estimation
    Seth Pettie, Dingyu Wang, and Longhui Yin
    In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), Jul 2021
    DOI