{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:54Z","timestamp":1773481854991,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":94,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1408940, CCF-1629444, CCF-1718700, CCF-1910030, CCF-1918989, and CCF-1919223"],"award-info":[{"award-number":["CCF-1408940, CCF-1629444, CCF-1718700, CCF-1910030, CCF-1918989, and CCF-1919223"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400227","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"89-102","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Optimal Parallel Algorithms in the Binary-Forking Model"],"prefix":"10.1145","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, D.C., DC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The Data Locality of Work Stealing. Theoretical Computer Science (TCS)","volume":"35","author":"Acar U. A.","year":"2002","unstructured":"U. A. Acar , G. E. Blelloch , and R. D. Blumofe . 2002 . The Data Locality of Work Stealing. Theoretical Computer Science (TCS) , Vol. 35 , 3 ( 2002 ). U. A. Acar, G. E. Blelloch, and R. D. Blumofe. 2002. The Data Locality of Work Stealing. Theoretical Computer Science (TCS), Vol. 35, 3 (2002)."},{"key":"e_1_3_2_1_2_1","volume-title":"Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. In ACM Conference on Programming Language Design and Implementation (PLDI). 769--782","author":"Acar Umut A.","year":"2018","unstructured":"Umut A. Acar , Arthur Chargu\u00e9raud , Adrien Guatto , Mike Rainey , and Filip Sieczkowski . 2018 . Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. In ACM Conference on Programming Language Design and Implementation (PLDI). 769--782 . Umut A. Acar, Arthur Chargu\u00e9raud, Adrien Guatto, Mike Rainey, and Filip Sieczkowski. 2018. Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. In ACM Conference on Programming Language Design and Implementation (PLDI). 769--782."},{"key":"e_1_3_2_1_3_1","volume-title":"Provably Good Scheduling for Parallel Programs That Use Data Structures Through Implicit Batching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Agrawal Kunal","year":"2014","unstructured":"Kunal Agrawal , Jeremy T. Fineman , Kefu Lu , Brendan Sheridan , Jim Sukha , and Robert Utterback . 2014 . Provably Good Scheduling for Parallel Programs That Use Data Structures Through Implicit Batching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Kunal Agrawal, Jeremy T. Fineman, Kefu Lu, Brendan Sheridan, Jim Sukha, and Robert Utterback. 2014. Provably Good Scheduling for Parallel Programs That Use Data Structures Through Implicit Batching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_4_1","volume-title":"Parallel Working-Set Search Structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Agrawal Kunal","year":"2018","unstructured":"Kunal Agrawal , Seth Gilbert , and Wei Quan Lim . 2018 . Parallel Working-Set Search Structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Kunal Agrawal, Seth Gilbert, and Wei Quan Lim. 2018. Parallel Working-Set Search Structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_5_1","volume-title":"Fast Parallel Operations on Search Trees. In IEEE International Conference on High Performance Computing (HiPC).","author":"Akhremtsev Yaroslav","year":"2016","unstructured":"Yaroslav Akhremtsev and Peter Sanders . 2016 . Fast Parallel Operations on Search Trees. In IEEE International Conference on High Performance Computing (HiPC). Yaroslav Akhremtsev and Peter Sanders. 2016. Fast Parallel Operations on Search Trees. In IEEE International Conference on High Performance Computing (HiPC)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00198-0"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/97444.97674"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90196-5"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_4"},{"key":"e_1_3_2_1_11_1","volume-title":"Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems (TOCS)","volume":"34","author":"Arora N. S.","year":"2001","unstructured":"N. S. Arora , R. D. Blumofe , and C. G. Plaxton . 2001 . Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems (TOCS) , Vol. 34 , 2 (01 Apr 2001 ). N. S. Arora, R. D. Blumofe, and C. G. Plaxton. 2001. Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems (TOCS), Vol. 34, 2 (01 Apr 2001)."},{"key":"e_1_3_2_1_12_1","unstructured":"Sara Baase. 1993. Introduction to Parallel Connectivity List Ranking and Euler Tour Techniques. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann 61--114.  Sara Baase. 1993. Introduction to Parallel Connectivity List Ranking and Euler Tour Techniques. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann 61--114."},{"key":"e_1_3_2_1_13_1","volume-title":"Parallel Algorithms for Asymmetric Read-Write Costs. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Ben-David Naama","year":"2016","unstructured":"Naama Ben-David , Guy E. Blelloch , Jeremy T. Fineman , Phillip B. Gibbons , Yan Gu , Charles McGuffey , and Julian Shun . 2016 . Parallel Algorithms for Asymmetric Read-Write Costs. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun. 2016. Parallel Algorithms for Asymmetric Read-Write Costs. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_14_1","volume-title":"Implicit Decomposition for Write-Efficient Connectivity Algorithms. In IEEE International Parallel and Distributed Processing Symposium (IPDPS).","author":"Ben-David Naama","year":"2018","unstructured":"Naama Ben-David , Guy E Blelloch , Jeremy T Fineman , Phillip B Gibbons , Yan Gu , Charles McGuffey , and Julian Shun . 2018 . Implicit Decomposition for Write-Efficient Connectivity Algorithms. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). Naama Ben-David, Guy E Blelloch, Jeremy T Fineman, Phillip B Gibbons, Yan Gu, Charles McGuffey, and Julian Shun. 2018. Implicit Decomposition for Write-Efficient Connectivity Algorithms. In IEEE International Parallel and Distributed Processing Symposium (IPDPS)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323210"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"e_1_3_2_1_18_1","unstructured":"Guy E. Blelloch. 1993. Prefix Sums and Their Applications. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann.  Guy E. Blelloch. 1993. Prefix Sums and Their Applications. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_20_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Blelloch Guy E.","year":"2008","unstructured":"Guy E. Blelloch , Rezaul Alam Chowdhury , Phillip B. Gibbons , Vijaya Ramachandran , Shimin Chen , and Michael Kozuch . 2008 . Provably good multicore cache performance for divide-and-conquer algorithms . In ACM-SIAM Symposium on Discrete Algorithms (SODA). Guy E. Blelloch, Rezaul Alam Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, and Michael Kozuch. 2008. Provably good multicore cache performance for divide-and-conquer algorithms. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_21_1","volume-title":"Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E","year":"2016","unstructured":"Guy E Blelloch , Daniel Ferizovic , and Yihan Sun . 2016 a. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E Blelloch, Daniel Ferizovic, and Yihan Sun. 2016a. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_22_1","volume-title":"Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch , Daniel Ferizovic , and Yihan Sun . 2016 b. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016b. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_3_2_1_24_1","volume-title":"Scheduling Irregular Parallel Computations on Hierarchical Caches. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2011","unstructured":"Guy E. Blelloch , Jeremy T. Fineman , Phillip B. Gibbons , and Harsha Vardhan Simhadri . 2011 . Scheduling Irregular Parallel Computations on Hierarchical Caches. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2011. Scheduling Irregular Parallel Computations on Hierarchical Caches. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_26_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Guy","unstructured":"Guy E. Blelloch and Phillip B. Gibbons. 2004. Effectively sharing a cache among threads . In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E. Blelloch and Phillip B. Gibbons. 2004. Effectively sharing a cache among threads. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301974"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_3_2_1_29_1","volume-title":"Parallelism in Randomized Incremental Algorithms. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E","year":"2016","unstructured":"Guy E Blelloch , Yan Gu , Julian Shun , and Yihan Sun . 2016 c. Parallelism in Randomized Incremental Algorithms. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E Blelloch, Yan Gu, Julian Shun, and Yihan Sun. 2016c. Parallelism in Randomized Incremental Algorithms. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_30_1","volume-title":"Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E","year":"2018","unstructured":"Guy E Blelloch , Yan Gu , Julian Shun , and Yihan Sun . 2018 . Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E Blelloch, Yan Gu, Julian Shun, and Yihan Sun. 2018. Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400255"},{"key":"e_1_3_2_1_32_1","volume-title":"Fast Set Operations Using Treaps. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Guy","unstructured":"Guy E. Blelloch and Margaret Reid-Miller. 1998 . Fast Set Operations Using Treaps. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E. Blelloch and Margaret Reid-Miller. 1998. Fast Set Operations Using Treaps. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000117"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312024"},{"key":"e_1_3_2_1_35_1","volume-title":"Leiserson","author":"Blumofe Robert D.","year":"1998","unstructured":"Robert D. Blumofe and Charles E . Leiserson . 1998 . Space-Efficient Scheduling of Multithreaded Computations. SIAM J. Scientific Computing , Vol. 27 , 1 (1998). Robert D. Blumofe and Charles E. Leiserson. 1998. Space-Efficient Scheduling of Multithreaded Computations. SIAM J. Scientific Computing, Vol. 27, 1 (1998)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Anastasia Braginsky and Erez Petrank. 2012. A lock-free B  Anastasia Braginsky and Erez Petrank. 2012. A lock-free B","DOI":"10.1145\/2312005.2312016"},{"key":"e_1_3_2_1_39_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 58--67","unstructured":"tree. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 58--67 . tree. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 58--67."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209045"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048147.2048198"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087586"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.04.008"},{"key":"e_1_3_2_1_45_1","article-title":"Parallel Merge Sort","volume":"17","author":"Cole Richard","year":"1988","unstructured":"Richard Cole . 1988 . Parallel Merge Sort . SIAM J. Scientific Computing , Vol. 17 , 4 (1988). Richard Cole. 1988. Parallel Merge Sort. SIAM J. Scientific Computing, Vol. 17, 4 (1988).","journal-title":"SIAM J. Scientific Computing"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087572"},{"key":"e_1_3_2_1_47_1","article-title":"Resource Oblivious Sorting on Multicores","volume":"3","author":"Cole Richard","year":"2017","unstructured":"Richard Cole and Vijaya Ramachandran . 2017 b. Resource Oblivious Sorting on Multicores . ACM Transactions on Parallel Computing (TOPC) , Vol. 3 , 4 (2017). Richard Cole and Vijaya Ramachandran. 2017b. Resource Oblivious Sorting on Multicores. ACM Transactions on Parallel Computing (TOPC), Vol. 3, 4 (2017).","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"e_1_3_2_1_48_1","volume-title":"Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms. In ACM Symposium on Theory of Computing (STOC). 206--219","author":"Cole Richard","year":"1986","unstructured":"Richard Cole and Uzi Vishkin . 1986 . Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms. In ACM Symposium on Theory of Computing (STOC). 206--219 . Richard Cole and Uzi Vishkin. 1986. Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms. In ACM Symposium on Theory of Computing (STOC). 206--219."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217009"},{"key":"e_1_3_2_1_50_1","volume-title":"Faster optimal parallel prefix sums and list ranking. Information and computation","author":"Cole Richard","year":"1989","unstructured":"Richard Cole and Uzi Vishkin . 1989. Faster optimal parallel prefix sums and list ranking. Information and computation , Vol. 81 , 3 ( 1989 ), 334--352. Richard Cole and Uzi Vishkin. 1989. Faster optimal parallel prefix sums and list ranking. Information and computation, Vol. 81, 3 (1989), 334--352."},{"key":"e_1_3_2_1_51_1","volume-title":"Bader","author":"Cong Guojing","year":"2005","unstructured":"Guojing Cong and David A . Bader . 2005 . An Empirical Analysis of Parallel Random Permutation Algorithms ON SMPs. In Parallel and Distributed Computing and Systems (PDCS) . Guojing Cong and David A. Bader. 2005. An Empirical Analysis of Parallel Random Permutation Algorithms ON SMPs. In Parallel and Distributed Computing and Systems (PDCS)."},{"key":"e_1_3_2_1_52_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd edition) .MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition) .MIT Press.","edition":"3"},{"key":"e_1_3_2_1_53_1","volume-title":"Fast generation of random permutations via networks simulation. Algorithmica","author":"Czumaj Artur","year":"1998","unstructured":"Artur Czumaj , Przemyslawa Kanarek , Miroslaw Kutylowski , and Krzysztof Lorys . 1998. Fast generation of random permutations via networks simulation. Algorithmica ( 1998 ). Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, and Krzysztof Lorys. 1998. Fast generation of random permutations via networks simulation. Algorithmica (1998)."},{"key":"e_1_3_2_1_54_1","volume-title":"Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Dhulipala Laxman","year":"2018","unstructured":"Laxman Dhulipala , Guy E. Blelloch , and Julian Shun . 2018 . Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018. Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB)","volume":"13","author":"Dhulipala Laxman","year":"2020","unstructured":"Laxman Dhulipala , Charlie McGuffey , Hongbo Kang , Yan Gu , Guy E Blelloch , Phillip B Gibbons , and Julian Shun . 2020 . Semi-Asymmetric Parallel Graph Algorithms for NVRAMs . Proceedings of the VLDB Endowment (PVLDB) , Vol. 13 , 9 (2020). Laxman Dhulipala, Charlie McGuffey, Hongbo Kang, Yan Gu, Guy E Blelloch, Phillip B Gibbons, and Julian Shun. 2020. Semi-Asymmetric Parallel Graph Algorithms for NVRAMs. Proceedings of the VLDB Endowment (PVLDB), Vol. 13, 9 (2020)."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935797"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/364520.364540"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323197"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_5"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/321592.321600"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0079"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPDP.1991.218302"},{"key":"e_1_3_2_1_65_1","volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Gil J.","unstructured":"J. Gil , Y. Matias , and U. Vishkin . 1991. Towards a theory of nearly constant time parallel algorithms . In IEEE Symposium on Foundations of Computer Science (FOCS). J. Gil, Y. Matias, and U. Vishkin. 1991. Towards a theory of nearly constant time parallel algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_66_1","volume-title":"Parallel Finger Search Structures. arXiv preprint arXiv:1908.02741","author":"Gilbert Seth","year":"2019","unstructured":"Seth Gilbert and Wei Quan Lim . 2019. Parallel Finger Search Structures. arXiv preprint arXiv:1908.02741 ( 2019 ). Seth Gilbert and Wei Quan Lim. 2019. Parallel Finger Search Structures. arXiv preprint arXiv:1908.02741 (2019)."},{"key":"e_1_3_2_1_67_1","volume-title":"Optimal Parallel Approximation for Prefix Sums and Integer Sorting. In ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Goodrich Michael T.","year":"1994","unstructured":"Michael T. Goodrich , Yossi Matias , and Uzi Vishkin . 1994 . Optimal Parallel Approximation for Prefix Sums and Integer Sorting. In ACM-SIAM Symposium on Discrete Algorithms (SODA). Michael T. Goodrich, Yossi Matias, and Uzi Vishkin. 1994. Optimal Parallel Approximation for Prefix Sums and Integer Sorting. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777454"},{"key":"e_1_3_2_1_70_1","volume-title":"Engineering Parallel In-place Random Generation of Integer Permutations. In Workshop on Experimental Algorithmics.","author":"Gustedt Jens","year":"2008","unstructured":"Jens Gustedt . 2008 . Engineering Parallel In-place Random Generation of Integer Permutations. In Workshop on Experimental Algorithmics. Jens Gustedt. 2008. Engineering Parallel In-place Random Generation of Integer Permutations. In Workshop on Experimental Algorithmics."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54233-7_151"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201004"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_33"},{"key":"e_1_3_2_1_75_1","volume-title":"Introduction to Parallel Algorithms","author":"JaJa J.","unstructured":"J. JaJa . 1992. Introduction to Parallel Algorithms . Addison-Wesley Professional . J. JaJa. 1992. Introduction to Parallel Algorithms .Addison-Wesley Professional."},{"key":"e_1_3_2_1_76_1","volume-title":"Karp and Vijaya Ramachandran","author":"Richard","year":"1990","unstructured":"Richard M. Karp and Vijaya Ramachandran . 1990 . Parallel Algorithms for Shared-Memory Machines. In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity (A). MIT Press. Richard M. Karp and Vijaya Ramachandran. 1990. Parallel Algorithms for Shared-Memory Machines. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A). MIT Press."},{"key":"e_1_3_2_1_77_1","volume-title":"The Art of Computer Programming, Volume II: Seminumerical Algorithms","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1969. The Art of Computer Programming, Volume II: Seminumerical Algorithms . Addison-Wesley . Donald E. Knuth. 1969. The Art of Computer Programming, Volume II: Seminumerical Algorithms .Addison-Wesley."},{"key":"e_1_3_2_1_78_1","volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS). 478--489","author":"Miller G.L.","unstructured":"G.L. Miller and J.H. Reif . 1985. Parallel tree contraction and its application . In IEEE Symposium on Foundations of Computer Science (FOCS). 478--489 . G.L. Miller and J.H. Reif. 1985. Parallel tree contraction and its application. In IEEE Symposium on Foundations of Computer Science (FOCS). 478--489."},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210388"},{"key":"e_1_3_2_1_80_1","article-title":"Binary search trees of bounded balance","volume":"2","author":"Nievergelt J\u00fcrg","year":"1973","unstructured":"J\u00fcrg Nievergelt and Edward M Reingold . 1973 . Binary search trees of bounded balance . SIAM J. Scientific Computing , Vol. 2 , 1 (1973). J\u00fcrg Nievergelt and Edward M Reingold. 1973. Binary search trees of bounded balance. SIAM J. Scientific Computing, Vol. 2, 1 (1973).","journal-title":"SIAM J. Scientific Computing"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00287-5"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036940"},{"key":"e_1_3_2_1_83_1","article-title":"Optimal and sublogarithmic time randomized parallel sorting algorithms","volume":"18","author":"Rajasekaran S.","year":"1989","unstructured":"S. Rajasekaran and J. H. Reif . 1989 . Optimal and sublogarithmic time randomized parallel sorting algorithms . SIAM J. Scientific Computing , Vol. 18 , 3 (1989). S. Rajasekaran and J. H. Reif. 1989. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. Scientific Computing, Vol. 18, 3 (1989).","journal-title":"SIAM J. Scientific Computing"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/HIPC.1998.737971"},{"key":"e_1_3_2_1_85_1","unstructured":"Margaret Reid-Miller Gary L. Miller and Francesmary Modugno. 1993. List Ranking and Parallel Tree Contraction. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann 115--194.  Margaret Reid-Miller Gary L. Miller and Francesmary Modugno. 1993. List Ranking and Parallel Tree Contraction. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann 115--194."},{"key":"e_1_3_2_1_86_1","unstructured":"John H. Reif. 1993. Synthesis of Paralell Algorithms .Morgan Kaufmann.  John H. Reif. 1993. Synthesis of Paralell Algorithms .Morgan Kaufmann."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90010-9"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.30"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688514"},{"key":"e_1_3_2_1_91_1","volume-title":"Data Structures and Network Algorithms","author":"Tarjan Robert Endre","unstructured":"Robert Endre Tarjan . 1983. Data Structures and Network Algorithms . Society for Industrial and Applied Mathematics , Philadelphia, PA, USA . Robert Endre Tarjan. 1983. Data Structures and Network Algorithms .Society for Industrial and Applied Mathematics, Philadelphia, PA, USA."},{"key":"e_1_3_2_1_92_1","volume-title":"Handbook of Theoretical Computer Science (Vol. A), Jan van Leeuwen (Ed.)","author":"Valiant L. G.","unstructured":"L. G. Valiant . 1990. General Purpose Parallel Architectures . In Handbook of Theoretical Computer Science (Vol. A), Jan van Leeuwen (Ed.) . MIT Press , 943--973. L. G. Valiant. 1990. General Purpose Parallel Architectures. In Handbook of Theoretical Computer Science (Vol. A), Jan van Leeuwen (Ed.). MIT Press, 943--973."},{"key":"e_1_3_2_1_93_1","volume-title":"Randomized Speed-Ups in Parallel Computation. In ACM Symposium on Theory of Computing (STOC). 230--239","author":"Vishkin Uzi","year":"1984","unstructured":"Uzi Vishkin . 1984 . Randomized Speed-Ups in Parallel Computation. In ACM Symposium on Theory of Computing (STOC). 230--239 . Uzi Vishkin. 1984. Randomized Speed-Ups in Parallel Computation. In ACM Symposium on Theory of Computing (STOC). 230--239."},{"key":"e_1_3_2_1_94_1","unstructured":"Uzi Vishkin. 1993. Advanced Parallel Prefix-sums List Ranking and Connectivity. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann 215--257.  Uzi Vishkin. 1993. Advanced Parallel Prefix-sums List Ranking and Connectivity. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann 215--257."}],"event":{"name":"SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400227","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:35Z","timestamp":1750202015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":94,"alternative-id":["10.1145\/3350755.3400227","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400227","relation":{},"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2020-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}