Publications - Papers with significant theoretical contribution

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

[Back to full publication list]

• 2023:
  [23] 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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023
  
  PIM-trie
  Conference paper  
• [22] 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
  
  Work, span, and space optimal parallel biconnectivity
  Conference paper  Full version (arXiv)  Code
• 2022:
  [21] 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
  
  new and improved bounds for parallel nearest neighbor search using cover tree
  Conference paper  
• [20] 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
  
  new and improved bounds for parallel LIS and MIS
  Conference paper  Full version (arXiv)  
• [19] 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
  
  New simplified analysis for RWS, and improved parallel cache bounds
  Conference paper  Full version (arXiv)  
• 2021:
  [18] 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
  
  Parameterized bounds for parallel SSSP
  Conference paper  Full version (arXiv)  Video  Code
• [17] Parallel In-Place Algorithms: Theory and Practice
  Yan Gu, Omar Obeya, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021
  
  New strong and relaxed parallel in-place algorithms
  Conference paper  Video  Code
• [16] The Read-Only Semi-External Model
  Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu, Charlie McGuffey, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021
  
  new bounds for various graph algorithms
  Conference paper  
• 2020:
  [15] 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.
  
  work and span optimal algorithms (sorting, semisorting, list/tree contraction, set-set algorithms) in the binary-forking model
  Conference 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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
  
  Work-efficient parallel incremental convexhull algorithm with polylog span
  Conference paper  Video  
• [13] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM)
  
  Parallel work-efficient algorithms with low span for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
  Conference paper  Journal paper  
• [12] Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming
  Guy Blelloch and Yan Gu
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2020
  
  New lower bounds and improved cache upper bounds for DP and algebra algorithms
  Conference 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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018
  
  Parallel write-efficient algorithms on Delaunay triangulation, k-d trees, interval tree, priority search tree, range tree
  Conference paper  Full version (arXiv)  
• [10] Implicit Decomposition for Write-Efficient Connectivity Algorithms
  Naama Ben-David, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  IPDPS
   IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018
  
  BC labeling for biconnectivity, graph decomposition with a limited size
  Conference paper  Full version (arXiv)  
• 2017:
  [9] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
  
  Proposed 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 Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  New parallel SSSP algorithms with work-span trade-off
  Conference paper  
• [7] Parallelism in Randomized Incremental Algorithms
  Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  Parallel work-efficient algorithms with low span for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
  Conference paper  Full version (arXiv)  
• [6] Parallel Algorithms with Asymmetric Read and Write Costs
  Naama Ben-David, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  Improved parallel write-efficient algorithms for various problems
  Conference paper  
• [5] Efficient Algorithms with Asymmetric Read and Write Costs
  Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons Yan Gu, and Julian Shun
  
  ESA
   European Symposium on Algorithms (ESA), 2016
  
  Lower bounds and improved write-efficient algorithms for various problems
  Conference paper  Full version (arXiv)  
• 2015:
  [4] Sorting with Asymmetric Read and Write Costs
  Guy Blelloch, Jeremy Fineman, Phillip Gibbons Yan Gu, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015
  
  write-efficient algorithms for sorting and cache-oblivious algorithms
  Conference paper  Full version (arXiv)  
• [3] A Top-down Parallel Semisort
  Yan Gu, Julian Shun and Yihan Sun and Guy E. Blelloch
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015
  
  Work-efficient semisort algorithm with polylog span
  Conference paper  
• [2] Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
  Julian Shun, Yan Gu, Guy Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons.
  
  SODA
   ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 431-448, 2015
  
  Work-efficient polylog-span algorithms for random permutation, list/tree contraction
  Conference 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
   SWAT 2012. Discrete & Computational Geometry, 2013, 50(2), pp. 374-408
  
  First polynomial algorithms for a list of problems
  Full version