Publications - Theoretical Results

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

[Back to full publication list]

• 2024:
  [26] 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  [BibTeX]
  @inproceedings{ Ding2024Parallel,
  title = { Parallel and (Nearly) Work-Efficient Dynamic Programming },
  author = {Ding, Xiangyun and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
  work-efficient parallel solutions for LCS, OAT, convex/concave GLWS and GAP
  Paper   ArXiV  Code  Slides
• [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  [BibTeX]
  @inproceedings{ Dong2024Parallel,
  title = { Parallel Integer Sort: Theory and Practice },
  author = {Dong, Xiaojun and Dhulipala, Laxman and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
  DOI:
  10.1145/3627535.3638483    [copy]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  Proofs for parallel MSD sorting
  Paper   ArXiV  Code  Slides
• [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), 2024  [BibTeX]
  @inproceedings{ Wang2024Fast,
  title = { Fast and Space-Efficient Parallel Algorithms for Influence Maximization },
  author = {Wang, Letong and Ding, Xiangyun and Gu, Yan and Sun, Yihan},
  booktitle = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
  DOI:
  10.14778/3632093.3632104    [copy]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  parallel CELF data structures with efficient work and polylog span; sketch compression algorithm with controllable compression rate
  Paper   ArXiV  Code  
• 2023:
  [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  [BibTeX]
  @inproceedings{ Ding2023Efficient,
  title = { Efficient Parallel Output-Sensitive Edit Distance },
  author = {Ding, Xiangyun and Dong, Xiaojun and Gu, Yan and Liu, Youzhe and Sun, Yihan},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2023 }
  }

  [copy]
  
  
  DOI:
  10.4230/LIPIcs.ESA.2023.40    [copy]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  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  [BibTeX]
  @inproceedings{ Dong2023High-Performance,
  title = { High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems },
  author = {Dong, Xiaojun and Wu, Yunshu and Wang, Zhongqi and Dhulipala, Laxman and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
  DOI:
  10.1145/3558481.3591071    [copy]
  
  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  [BibTeX]
  @inproceedings{ Gu2023Parallel,
  title = { Parallel Longest Increasing Subsequence and van Emde Boas Trees },
  author = {Gu, Yan and Men, Ziyang and Shen, Zheqi and Sun, Yihan and Wan, Zijin},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
  DOI:
  10.1145/3558481.3591069    [copy]
  
  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  [BibTeX]
  @inproceedings{ Dong2023Provably,
  title = { Provably Fast and Space-Efficient Parallel Biconnectivity },
  author = {Dong, Xiaojun and Wang, Letong and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2023 }
  }

  [copy]
  
  
  DOI:
  10.1145/3572848.3577483    [copy]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  
  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  [BibTeX]
  @inproceedings{ Gu2022Parallel,
  title = { Parallel Cover Trees and Applications },
  author = {Gu, Yan and Napier, Zachary and Sun, Yihan and Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3490148.3538581    [copy]
  
  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  [BibTeX]
  @inproceedings{ Shen2022Many,
  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]
  
  
  DOI:
  10.1145/3490148.3538574    [copy]
  
  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  [BibTeX]
  @inproceedings{ Dhulipala2022PaC-trees:,
  title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
  author = {Dhulipala, Laxman and Blelloch, Guy and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3519939.3523733    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2022Joinable,
  title = { Joinable Parallel Balanced Binary Trees },
  author = {Blelloch, Guy E. and Ferizovic, Daniel and Sun, Yihan},
  booktitle = {ACM Transactions on Parallel Computing (TOPC)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3512769    [copy]
  
  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  [BibTeX]
  @inproceedings{ Gu2022Analysis,
  title = { Analysis of Work-Stealing and Parallel Cache Complexity },
  author = {Gu, Yan and Napier, Zachary and Sun, Yihan},
  booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1137/1.9781611977059.4    [copy]
  
  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  [BibTeX]
  @inproceedings{ Ben-David2021Space,
  title = { Space and Time Bounded Multiversion Garbage Collection },
  author = {Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan and Wei, Yuanhao},
  booktitle = {International Symposium on Distributed Computing (DISC)},
  year = { 2021 }
  }

  [copy]
  
  
  DOI:
  10.4230/LIPIcs.DISC.2021.12    [copy]
  
  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  [BibTeX]
  @inproceedings{ Dong2021Efficient,
  title = { Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths },
  author = {Dong, Xiaojun and Gu, Yan and Sun, Yihan and Zhang, Yunming},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2021 }
  }

  [copy]
  
  
  DOI:
  10.1145/3409964.3461782    [copy]
  
  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  [BibTeX]
  @inproceedings{ Wei2021Constant-Time,
  title = { Constant-Time Snapshots with Applications to Concurrent Data Structures },
  author = {Wei, Yuanhao and Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2021 }
  }

  [copy]
  
  
  DOI:
  10.1145/3437801.3441602    [copy]
  
  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 (Best paper finalist)!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020  [BibTeX]
  @inproceedings{ Blelloch2020Optimal,
  title = { Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model },
  author = {Blelloch, Guy E. and Fineman, Jeremy and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
  DOI:
  10.1145/3350755.3400227    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2020Randomized,
  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]
  
  
  DOI:
  10.1145/3350755.3400255    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2020Parallelism,
  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]
  
  
  DOI:
  10.1145/3402819    [copy]
  
  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  [BibTeX]
  @inproceedings{ Ben-David2019Multiversion,
  title = { Multiversion Concurrency with Bounded Delay and Precise Garbage Collection },
  author = {Ben-David, Naama and Blelloch, Guy E. and Sun, Yihan and Wei, Yuanhao},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.1145/3323165.3323185    [copy]
  
  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  [BibTeX]
  @inproceedings{ Sun2019Parallel,
  title = { Parallel Range, Segment and Rectangle Queries with Augmented Maps },
  author = {Sun, Yihan and Blelloch, Guy E.},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.1137/1.9781611975499.13    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2018Parallel,
  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]
  
  
  DOI:
  10.1145/3210377.3210380    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2017Efficient,
  title = { Efficient Construction of Probabilistic Tree Embeddings },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan},
  booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
  year = { 2017 }
  }

  [copy]
  
  
  DOI:
  10.4230/LIPIcs.ICALP.2017.26    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2016Just,
  title = { Just Join for Parallel Ordered Sets },
  author = {Blelloch, Guy E. and Ferizovic, Daniel and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
  DOI:
  10.1145/2935764.2935768    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2016Parallel,
  title = { Parallel Shortest-paths Using Radius Stepping },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan and Tangwongsan, Kanat},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
  DOI:
  10.1145/2935764.2935765    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2016Parallelism,
  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]
  
  
  DOI:
  10.1145/2935764.2935766    [copy]
  
  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  [BibTeX]
  @inproceedings{ Gu2015A,
  title = { A Top-down Parallel Semisort },
  author = {Gu, Yan and Shun, Julian and Sun, Yihan and Blelloch, Guy E.},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2015 }
  }

  [copy]
  
  
  Work-efficient semisort algorithm with polylog span
  Paper   Slides