Publications - Theoretical Results

You can also find my publication list on Google Scholar and DBLP.

[Back to full publication list]

  • 2024:
    [25] Parallel Integer Sort: Theory and Practice
    Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024  
    DOI:
    10.1145/3627535.3638483   
    Proofs for parallel MSD sorting
    Paper   ArXiV  Code  
  • 2023:
    [24] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
    Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
    VLDB
     Proceedings of the VLDB Endowment (VLDB), 2023  
    DOI:
    10.14778/3632093.3632104   
    parallel CELF data structures with efficient work and polylog span; sketch compression algorithm with controlable compression rate
    Paper   ArXiV  Code  
  • [23] Efficient Parallel Output-Sensitive Edit Distance
    Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun
    🏆 Best Paper Award!
    ESA
     European Symposium on Algorithms (ESA), 2023  
    DOI:
    10.4230/LIPIcs.ESA.2023.40   
    output-sensitive edit distance algorithms
    Paper   ArXiV  Code  Slides
  • [22] High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
    Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023  
    DOI:
    10.1145/3558481.3591071   
    work, span and I/O bounds and their tradeoffs for parallel semisort
    Paper   ArXiV  Code  Slides
  • [21] Parallel Longest Increasing Subsequence and van Emde Boas Trees
    Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023  
    DOI:
    10.1145/3558481.3591069   
    new parallel LIS algorithm with efficient work; parallel batch updtes on vEB tree with efficient work and polylog span
    Paper   ArXiV  Code  Slides
  • [20] Provably Fast and Space-Efficient Parallel Biconnectivity
    Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun
    🏆 Best Paper Award!
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023  
    DOI:
    10.1145/3572848.3577483   
    Work-, span- and space-efficient algorithm and implementation of parallel biconnected components
    Paper   ArXiV  Code  Slides
  • 2022:
    [19] Parallel Cover Trees and Applications
    Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022  
    DOI:
    10.1145/3490148.3538581   
    New and improved bounds for parallel nearest neighbor search using cover tree
    Paper   Slides
  • [18] Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
    Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022  
    DOI:
    10.1145/3490148.3538574   
    New and improved bounds for parallel LIS and MIS
    Paper   ArXiV  Slides
  • [17] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
    Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
    PLDI
     ACM Conference on Programming Language Design and Implementation (PLDI), 2022  
    DOI:
    10.1145/3519939.3523733   
    Provably efficient parallel batch algorithms for compressed functional search trees
    Paper   ArXiV  Code  Slides
  • [16] Joinable Parallel Balanced Binary Trees
    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
    TOPC
     ACM Transactions on Parallel Computing (TOPC), 2022  
    DOI:
    10.1145/3512769   
    Cost bound of join-based algorithms and general proofs for multiple balancing schemes.
    Paper   Code  
  • [15] Analysis of Work-Stealing and Parallel Cache Complexity
    Yan Gu, Zachary Napier, and Yihan Sun
    APOCS
     ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2022  
    DOI:
    10.1137/1.9781611977059.4   
    New simplified analysis for work-stealing scheduler and improvded parallel cache bounds.
    Paper   
  • 2021:
    [14] Space and Time Bounded Multiversion Garbage Collection
    Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei
    DISC
     International Symposium on Distributed Computing (DISC), 2021  
    DOI:
    10.4230/LIPIcs.DISC.2021.12   
    Time and space bound for GC algorithms
    Paper   Video  ArXiV  
  • [13] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
    Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021  
    DOI:
    10.1145/3409964.3461782   
    Parameterized bounds for parallel SSSP
    Paper   Video  ArXiV  Code  
  • [12] Constant-Time Snapshots with Applications to Concurrent Data Structures
    Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021  
    DOI:
    10.1145/3437801.3441602   
    constant-time algorithm to make CAS-based data structures to snapshottable
    Paper   Video  ArXiV  Code  
  • 2020:
    [11] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
    Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun
    🏆 Outstanding Paper Award!
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020  
    DOI:
    10.1145/3350755.3400227   
    work and span optimal algorithms (sorting, semisorting, list/tree contraction, set algorithms) in the binary-forking model
    Paper   Video  
  • [10] Randomized Incremental Convex Hull is Highly Parallel
    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020  
    DOI:
    10.1145/3350755.3400255   
    Work-efficient parallel incremental convex hull algorithm with polylog span
    Paper   Video  
  • [9] Parallelism in Randomized Incremental Algorithms
    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    JACM
     Journal of the ACM (JACM), 2020  
    DOI:
    10.1145/3402819   
    Parallel work-efficient algorithms with low span
    Paper   
  • 2019:
    [8] Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
    Naama Ben-David, Guy E. Blelloch, Yihan Sun, and Yuanhao Wei
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019  
    DOI:
    10.1145/3323165.3323185   
    wait-free algorithm for garbage collection
    Paper   ArXiV  
  • [7] Parallel Range, Segment and Rectangle Queries with Augmented Maps
    Yihan Sun, and Guy E. Blelloch
    ALENEX
     Algorithm Engineering and Experiments (ALENEX), 2019  
    DOI:
    10.1137/1.9781611975499.13   
    Work-efficient parallel algorithms for range, segment and rectangle queries with low span
    Paper   ArXiV  
  • 2018:
    [6] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
    Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018  
    DOI:
    10.1145/3210377.3210380   
    Parallel write-efficient algorithms on Delaunay triangulation, k-d trees, interval tree, priority search tree, range tree
    Paper   ArXiV  
  • 2017:
    [5] Efficient Construction of Probabilistic Tree Embeddings
    Guy E. Blelloch, Yan Gu, and Yihan Sun
    ICALP
     International Colloquium on Automata, Languages, and Programming (ICALP), 2017  
    DOI:
    10.4230/LIPIcs.ICALP.2017.26   
    Proposed an efficient algorithm to construct probablistic tree embeddings with improved bounds.
    Paper   ArXiV  
  • 2016:
    [4] Just Join for Parallel Ordered Sets
    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016  
    DOI:
    10.1145/2935764.2935768   
    Work-efficient parallel set operations with low span
    Paper   ArXiV  Code  
  • [3] Parallel Shortest-paths Using Radius Stepping
    Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016  
    DOI:
    10.1145/2935764.2935765   
    New parallel SSSP algorithms with work-span trade-off
    Paper   
  • [2] Parallelism in Randomized Incremental Algorithms
    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016  
    DOI:
    10.1145/2935764.2935766   
    Parallel work-efficient algorithms with low span for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
    Paper   ArXiV  
  • 2015:
    [1] A Top-down Parallel Semisort
    Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015  

    Work-efficient semisort algorithm with polylog span
    Paper   Slides