{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:49:40Z","timestamp":1763459380633,"version":"3.45.0"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,11]],"date-time":"2017-07-11T00:00:00Z","timestamp":1499731200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1314590 and CCF-1533858"],"award-info":[{"award-number":["CCF-1314590 and CCF-1533858"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007247","name":"Adolph C. and Mary Sprague Miller Institute for Basic Research in Science, University of California Berkeley","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007247","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,7,11]]},"DOI":"10.1145\/2935764.2935766","type":"proceedings-article","created":{"date-parts":[[2016,7,8]],"date-time":"2016-07-08T11:03:00Z","timestamp":1467975780000},"page":"467-478","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Parallelism in Randomized Incremental Algorithms"],"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":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129744"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174661"},{"key":"e_1_3_2_1_3_1","first-page":"497","volume-title":"Synthesis of Parallel Algorithms","author":"Atallah M.","year":"1993","unstructured":"M. Atallah and M. Goodrich. Deterministic parallel computational geometry. In Synthesis of Parallel Algorithms, pages 497--536. Morgan Kaufmann, 1993."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.59"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137900"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_8_1","volume-title":"Efficient construction of probabilistic tree embeddings. arXiv preprint: 1605.04651","author":"Blelloch G. E.","year":"2016","unstructured":"G. E. Blelloch, Y. Gu, and Y. Sun. Efficient construction of probabilistic tree embeddings. arXiv preprint: 1605.04651, 2016."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935765"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312045"},{"key":"e_1_3_2_1_11_1","volume-title":"Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3--4):243--269","author":"Blelloch G. E.","year":"1999","unstructured":"G. E. Blelloch, J. C. Hardwick, G. L. Miller, and D. Talmor. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3--4):243--269, 1999."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855591.1855595"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90024-N"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_1_15_1","volume-title":"IEEE International Symposium on Workload Characterization (IISWC)","author":"Minh C. Cao","year":"2008","unstructured":"C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IEEE International Symposium on Workload Characterization (IISWC), 2008."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00028-1"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1230129"},{"key":"e_1_3_2_1_18_1","first-page":"188","volume-title":"International conference on computational science and its applications. In Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm","author":"Cintra M.","year":"2004","unstructured":"M. Cintra, D. R. Llanos, and B. Palop. International conference on computational science and its applications. In Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm, pages 188--197, 2004."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982816"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"D. Coppersmith L. Fleischer B. Hendrickson and A. Pinar. A divide-and-conquer algorithm for identifying strongly connected components. Technical Report RC23744 IBM 2003.","DOI":"10.2172\/889876"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90026-T"},{"key":"e_1_3_2_1_26_1","volume-title":"Jornadas De Paralelismo","author":"Diaz P.","year":"2004","unstructured":"P. Diaz, D. R. Llanos, and B. Palop. Parallelizing 2D-convex hulls on clusters: Sorting matters. Jornadas De Paralelismo, 2004."},{"key":"e_1_3_2_1_27_1","first-page":"3147","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Du N.","year":"2013","unstructured":"N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems (NIPS), pages 3147--3155, 2013."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220316"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1137760"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185438"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/642060.642062"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apm.2005.05.022"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/313852.313904"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009325"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/21.2.168"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758770"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612697"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503246"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/133889"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1049"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0888"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2005.49"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"e_1_3_2_1_48_1","volume-title":"Computational geometry - an introduction through randomized algorithms","author":"Mulmuley K.","year":"1994","unstructured":"K. Mulmuley. Computational geometry - an introduction through randomized algorithms. Prentice Hall, 1994."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969239.2969249"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_3_2_1_51_1","first-page":"21","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"Rabin M. O.","year":"1976","unstructured":"M. O. Rabin. Probabilistic algorithms. Algorithms and Complexity: New Directions and Recent Results, pages 21--39, 1976."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_3_2_1_54_1","volume-title":"Optimal randomized parallel algorithms for computational geometry. Algorithmica, 7(1--6):91--117","author":"Reif J. H.","year":"1992","unstructured":"J. H. Reif and S. Sen. Optimal randomized parallel algorithms for computational geometry. Algorithmica, 7(1--6):91--117, 1992."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378560"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574699"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58043-7_3"},{"key":"e_1_3_2_1_58_1","volume-title":"Department of Computer Science","author":"Sen S.","year":"1995","unstructured":"S. Sen. A deterministic poly(\u0142og\u0142og n) time optimal CRCW PRAM algorithm for linear programming in fixed dimensions. Technical report, Department of Computer Science, University of Newcastle, 1995."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722159"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265923"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_1_64_1","volume-title":"Texas A&M","author":"Tomkins D.","year":"2015","unstructured":"D. Tomkins, T. Smith, N. M. Amato, and L. Rauchwerger. Efficient, reachability-based, parallel algorithms for finding strongly connected components. Technical report, Texas A&M University, 2015."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220006"},{"key":"e_1_3_2_1_66_1","volume-title":"Some Basic Data-Parallel Algorithms and Techniques","author":"Vishkin U.","year":"2010","unstructured":"U. Vishkin. Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques. 2010."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0038202"}],"event":{"name":"SPAA '16: 28th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture"],"location":"Pacific Grove California USA","acronym":"SPAA '16"},"container-title":["Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2935764.2935766","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2935764.2935766","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2935764.2935766","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:44:17Z","timestamp":1763459057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2935764.2935766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,11]]},"references-count":67,"alternative-id":["10.1145\/2935764.2935766","10.1145\/2935764"],"URL":"https:\/\/doi.org\/10.1145\/2935764.2935766","relation":{},"subject":[],"published":{"date-parts":[[2016,7,11]]},"assertion":[{"value":"2016-07-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}