Parallel Dynamic Programming

[Back to full publication list]

Parallel dynamic programming algorithms, such as longest increasing subsequence (LIS), edit distance (ED), and various optimizations such as decision monotonicity and sparsity.

2024:
[6] 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 }
}

  Software Library:
Parallel Work-Efficient Dynamic Programming  [Github]
Paper   ArXiV  Code  Slides
2023:
[5] 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 }
}

  DOI:
10.4230/LIPIcs.ESA.2023.40
  Software Library:
Parallel Output-Sensitive Edit Distance  [Github]
HOPC
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
Paper   ArXiV  Code  Slides
[4] 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 }
}

  DOI:
10.1145/3558481.3591069
  Software Library:
Parallel Longest Increasing Subsequence  [Github]
Paper   ArXiV  Code  Slides
2022:
[3] 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 }
}

  DOI:
10.1145/3490148.3538574
  Software Library:
Parallel Dynamic Programming (DP) and greedy algorithms  [Github]
Paper   ArXiV  Slides
[2] 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 }
}

  DOI:
10.1137/1.9781611977059.4
Paper
2020:
[1] Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming
Yan Gu*, and Guy E. Blelloch
APOCS
ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2020 [BibTeX]

@inproceedings{ Gu2020Improved,
title = { Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming },
author = { Gu, Yan and Blelloch, Guy E.},
booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
year = { 2020 }
}

Paper ArXiV