[Back to full publication list]

• 2022:
  [6] 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    [BibTeX]
  @inproceedings{ iterative,
  title = { Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient },
  author = {Shen, Zheqi and Wan, Zijin and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
  Parallelizing sequential algorithms for LIS, activity selection, Huffman tree, MIS, and Dijkstra's algorithm.
  Paper   ArXiV  Slides  
• 2020:
  [5] 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    [BibTeX]
  @inproceedings{ convexhull,
  title = { Randomized Incremental Convex Hull is Highly Parallel },
  author = {Blelloch, Guy E. and Gu, Yan and Shun, Julian and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
  Parallel incremental algorithm for convex hull
  Paper   Video  
• [4] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM), 2020    [BibTeX]
  @inproceedings{ incremental-jacm,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = {Blelloch, Guy E. and Gu, Yan and Shun, Julian and Sun, Yihan},
  booktitle = {Journal of the ACM (JACM)},
  year = { 2020 }
  }

  [copy]
  
  
  Parallel incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
  Paper   
• 2018:
  [3] 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    [BibTeX]
  @inproceedings{ we-geo,
  title = { Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan and Shun, Julian},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2018 }
  }

  [copy]
  
  
  Parallel randomized incremental algorithm on Delaunay triangulation
  Paper   ArXiV  
• 2016:
  [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    [BibTeX]
  @inproceedings{ incremental,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = {Blelloch, Guy E. and Gu, Yan and Shun, Julian and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
  Parallel randomized incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
  Paper   ArXiV  
• 2015:
  [1] 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
  
  SODA
   ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015    [BibTeX]
  @inproceedings{ ,
  title = { Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel },
  author = {Shun, Julian and Gu, Yan and Blelloch, Guy E. and Fineman, Jeremy T. and Gibbons, Phillip B.},
  booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year = { 2015 }
  }

  [copy]
  
  
  Work-efficient polylog-span algorithms for random permutation, list/tree contraction
  Paper