Publications - Papers with significant theoretical contribution
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2027:[41]Parallel B+ Trees: Theory and Practice
Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2027 - 2026:[40]Parallel Metric Skip Lists and Nearest Neighbor Search
Xiangyun Ding, Rohin Garg, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2026
Conference paper - [39]Parallel Integer and Learning-Augmented Sorting Algorithms in the Binary-Forking Model
Michael T. Goodrich and Yan Gu
IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2026
Conference paper - [38]Parallel Dynamic Spatial Indexes
Ziyang Men, Bo Huang, Yan Gu, and Yihan Sun
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2026
Conference paper Full version (arXiv) Code - [37]PIM-zd-tree: A Fast Space-Partitioning Index Leveraging Processing-in-Memory
Yiwei Zhao, Hongbo Kang, Ziyang Men, Yan Gu, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2026
Conference paper - 2025:[36]Parallel Joinable B-Trees in the Fork-Join I/O Model
Michael T. Goodrich, Yan Gu, Ryuto Kitagawa, and Yihan Sun
International Symposium on Algorithms and Computation (ISAAC), 2025
Conference paper Full version (arXiv) - [35]Parallel Point-to-Point Shortest Paths and Batch Queries
Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025
Conference paper Full version (arXiv) Code - [34]Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications
Yiwei Zhao, Hongbo Kang, Yan Gu, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025
Conference paper - [33]New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
Xiangyun Ding, Yan Gu, and Yihan Sun
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025provable efficiency for incremental minimum spanning treesConference paper Code - [32]Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, and Yihan Sun🏆 Best Paper FinalistACM International Conference on Supercomputing (ICS), 2025
Conference paper Full version (arXiv) Code - [31]Parallel k-Core Decomposition: Theory and Practice
Youzhe Liu, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2025
Conference paper Full version (arXiv) Code - [30]Pkd-tree: Parallel kd-tree with Batch Updates
Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2025
Conference paper Full version Code - 2024:[29]Parallel and (Nearly) Work-Efficient Dynamic Programming
Xiangyun Ding, Yan Gu, and Yihan Sun🏆 Outstanding Paper Award (Best Paper Finalist)ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024
Conference paper Full version (arXiv) Code - [28]Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Laxman Dhulipala, Xiaojun Dong, Kishen Gowda, and Yan Gu
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024
Conference paper Full version (arXiv) Code - [27]Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
Proceedings of the VLDB Endowment (PVLDB), 17(3), 2024
Conference paper Full version (arXiv) Code - [26]Parallel Integer Sort: Theory and Practice
Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024
Conference paper Full version (arXiv) Code - 2023:[25]Efficient Parallel Output-Sensitive Edit Distance
Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun🏆 Best Paper AwardEuropean Symposium on Algorithms (ESA), 2023
Conference paper Full version (arXiv) Code - [24]PIM-trie: A Skew-resistant Trie for Processing-in-Memory
Hongbo Kang, Yiwei Zhao, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip B. Gibbons
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023PIM-trieConference paper - [23]Parallel Strong Connectivity Based on Faster Reachability
Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2023
Conference paper Full version (arXiv) Code - [22]Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun🏆 Best Paper AwardACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023Work, span, and space optimal parallel biconnectivityConference paper Full version (arXiv) Code - 2022:[21]Parallel Cover Trees and their Applications
Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022new and improved bounds for parallel nearest neighbor search using cover treeConference paper - [20]Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022new and improved bounds for parallel LIS and MISConference paper Full version (arXiv) - [19]Analysis of Work-Stealing and Parallel Cache Complexity
Yan Gu, Zachary Napier, and Yihan Sun
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2022New simplified analysis for RWS, and improved parallel cache boundsConference paper Full version (arXiv) - 2021:[18]Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021Parameterized bounds for parallel SSSPConference paper Full version (arXiv) Video Code - [17]Parallel In-Place Algorithms: Theory and Practice
Yan Gu, Omar Obeya, and Julian Shun
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021New strong and relaxed parallel in-place algorithmsConference paper Video Code - [16]The Read-Only Semi-External Model
Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021new bounds for various graph algorithmsConference paper - 2020:[15]Optimal Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun🏆 Outstanding Paper AwardACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020work and span optimal algorithms (sorting, semisorting, list/tree contraction, set-set algorithms) in the binary-forking modelConference paper Full version (arXiv) Video Full Video - [14]Randomized Incremental Convex Hull is Highly Parallel
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020Work-efficient parallel incremental convexhull algorithm with polylog spanConference paper Video - [13]Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Journal of the ACM (JACM), 67(5), 2020Parallel work-efficient algorithms with low span for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE listConference paper Journal paper - [12]Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming and Linear Algebra
Guy E. Blelloch and Yan Gu
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2020New lower bounds and improved cache upper bounds for DP and algebra algorithmsConference paper Full version (arXiv) - 2018:[11]Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018Parallel write-efficient algorithms on Delaunay triangulation, k-d trees, interval tree, priority search tree, range treeConference paper Full version (arXiv) - [10]Implicit Decomposition for Write-Efficient Connectivity Algorithms
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018BC labeling for biconnectivity, graph decomposition with a limited sizeConference paper Full version (arXiv) - 2017:[9]Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu, and Yihan Sun
International Colloquium on Automata, Languages, and Programming (ICALP), 2017Proposed an efficient algorithm to construct probablistic tree embeddings with improved bounds.Conference paper Full version (arXiv) - 2016:[8]Parallel Shortest-paths Using Radius Stepping
Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016New parallel SSSP algorithms with work-span trade-offConference paper - [7]Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016Parallel work-efficient algorithms with low span for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE listConference paper Full version (arXiv) - [6]Parallel Algorithms with Asymmetric Read and Write Costs
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016Improved parallel write-efficient algorithms for various problemsConference paper - [5]Efficient Algorithms with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun
European Symposium on Algorithms (ESA), 2016Lower bounds and improved write-efficient algorithms for various problemsConference paper Full version (arXiv) - 2015:[4]Sorting with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015write-efficient algorithms for sorting and cache-oblivious algorithmsConference paper Full version (arXiv) - [3]A Top-down Parallel Semisort
Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015Work-efficient semisort algorithm with polylog spanConference paper - [2]Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons
ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 431-448, 2015Work-efficient polylog-span algorithms for random permutation, list/tree contractionConference paper - 2013:[1]Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain
Danny Z. Chen, Yan Gu, Jian Li, and Haitao Wang
SWAT 2012. Discrete & Computational Geometry, 2013, 50(2), pp. 374-408First polynomial algorithms for a list of problemsConference paper Full version