Publications - Parallel Incremental Algorithms

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

[Back to full publication list]

  • 2024:
    [7] Parallel and (Nearly) Work-Efficient Dynamic Programming
    Xiangyun Ding, Yan Gu, and Yihan Sun
    🏆 Outstanding Paper Award (Best paper finalist)!
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024  
    parallelize iterative DP algorithms
    Paper   ArXiV  Code  Slides
  • 2023:
    [6] 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   
    Parallelizing sequential algorithms for LIS
    Paper   ArXiV  Code  Slides
  • 2022:
    [5] 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   
    Parallelizing sequential algorithms for LIS, activity selection, Huffman tree, MIS, and Dijkstra's algorithm.
    Paper   ArXiV  Slides
  • 2020:
    [4] 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   
    Parallel incremental algorithm for convex hull
    Paper   Video  
  • [3] 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 incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
    Paper   
  • 2018:
    [2] 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 randomized incremental algorithm on Delaunay triangulation
    Paper   ArXiV  
  • 2016:
    [1] 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 randomized incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
    Paper   ArXiV