{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T05:02:20Z","timestamp":1764133340638,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":65,"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:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400223","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"153-162","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Hardness of Massively Parallel Computation"],"prefix":"10.1145","author":[{"given":"Kai-Min","family":"Chung","sequence":"first","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan Roc"}]},{"given":"Kuan-Yi","family":"Ho","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}]},{"given":"Xiaorui","family":"Sun","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, Chicago, IL, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"277","volume-title":"Proceedings of the VLDB Endowment","volume":"6","author":"Afrati Foto N","year":"2013","unstructured":"Foto N Afrati , Anish Das Sarma , Semih Salihoglu , and Jeffrey D Ullman . Upper and lower bounds on the cost of a map-reduce computation . In Proceedings of the VLDB Endowment , volume 6 , pages 277 -- 288 . VLDB Endowment , 2013 . Foto N Afrati, Anish Das Sarma, Semih Salihoglu, and Jeffrey D Ullman. Upper and lower bounds on the cost of a map-reduce computation. In Proceedings of the VLDB Endowment, volume 6, pages 277--288. VLDB Endowment, 2013."},{"key":"e_1_3_2_1_2_1","volume-title":"Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing (TOPC), 4(4):17","author":"Ahn Kook Jin","year":"2018","unstructured":"Kook Jin Ahn and Sudipto Guha . Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing (TOPC), 4(4):17 , 2018 . Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing (TOPC), 4(4):17, 2018."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78375-8_4"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_13"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56617-7_2"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746622"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_9_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","author":"Andoni Alexandr","year":"2019","unstructured":"Alexandr Andoni , Clifford Stein , and Peilin Zhong . Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 , July 9 --12 , 2019 , Patras, Greece, 2019. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9--12, 2019, Patras, Greece, 2019."},{"key":"e_1_3_2_1_10_1","volume-title":"Simple round compression for parallel vertex cover. CoRR, abs\/1709.04599","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi . Simple round compression for parallel vertex cover. CoRR, abs\/1709.04599 , 2017 . Sepehr Assadi. Simple round compression for parallel vertex cover. CoRR, abs\/1709.04599, 2017."},{"key":"e_1_3_2_1_11_1","volume-title":"Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab Mirrokni , and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , San Diego, California, USA, January 6--9 , 2019 , 2017. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6--9, 2019, 2017."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319697"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087581"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180915"},{"key":"e_1_3_2_1_17_1","volume-title":"Massively parallel dynamic programming on trees. arXiv preprint arXiv:1809.03685","author":"Bateni MohammadHossein","year":"2018","unstructured":"MohammadHossein Bateni , Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , and Vahab Mirrokni . Massively parallel dynamic programming on trees. arXiv preprint arXiv:1809.03685 , 2018 . MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab Mirrokni. Massively parallel dynamic programming on trees. arXiv preprint arXiv:1809.03685, 2018."},{"key":"e_1_3_2_1_18_1","first-page":"2591","volume-title":"Advances in Neural Information Processing Systems","author":"Bateni MohammadHossein","year":"2014","unstructured":"MohammadHossein Bateni , Aditya Bhaskara , Silvio Lattanzi , and Vahab Mirrokni . Distributed balanced clustering via mapping coresets . In Advances in Neural Information Processing Systems , pages 2591 -- 2599 , 2014 . MohammadHossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab Mirrokni. Distributed balanced clustering via mapping coresets. In Advances in Neural Information Processing Systems, pages 2591--2599, 2014."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_20_1","volume-title":"Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. CoRR, abs\/1807.06701","author":"Behnezhad Soheil","year":"2018","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , and Richard M. Karp . Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. CoRR, abs\/1807.06701 , 2018 . Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Richard M. Karp. Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. CoRR, abs\/1807.06701, 2018."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00096"},{"key":"e_1_3_2_1_22_1","first-page":"171","volume-title":"International Conference on the Theory and Applications of Cryptographic Techniques","author":"Bellare Mihir","year":"2004","unstructured":"Mihir Bellare , Alexandra Boldyreva , and Adriana Palacio . An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In Advances in Cryptology - EUROCRYPT 2004 , International Conference on the Theory and Applications of Cryptographic Techniques , Interlaken, Switzerland, May 2--6 , 2004 , Proceedings, pages 171 -- 188 , 2004. Mihir Bellare, Alexandra Boldyreva, and Adriana Palacio. An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2--6, 2004, Proceedings, pages 171--188, 2004."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382279"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_1_25_1","first-page":"92","volume-title":"Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9--12, 1994","author":"Bellare Mihir","year":"1994","unstructured":"Mihir Bellare and Phillip Rogaway . Optimal asymmetric encryption . In Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9--12, 1994 , Proceedings , pages 92 -- 111 , 1994 . Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9--12, 1994, Proceedings, pages 92-- 111, 1994."},{"key":"e_1_3_2_1_26_1","first-page":"330","volume-title":"TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II","author":"Brakerski Zvika","year":"2016","unstructured":"Zvika Brakerski , David Cash , Rotem Tsabary , and Hoeteck Wee . Targeted homomorphic attribute-based encryption. In Theory of Cryptography - 14th International Conference , TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II , pages 330 -- 360 , 2016 . Zvika Brakerski, David Cash, Rotem Tsabary, and Hoeteck Wee. Targeted homomorphic attribute-based encryption. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, pages 330--360, 2016."},{"key":"e_1_3_2_1_27_1","volume-title":"Matching and MIS for uniformly sparse graphs in the low-memory MPC model. CoRR, abs\/1807.05374","author":"Brandt Sebastian","year":"2018","unstructured":"Sebastian Brandt , Manuela Fischer , and Jara Uitto . Matching and MIS for uniformly sparse graphs in the low-memory MPC model. CoRR, abs\/1807.05374 , 2018 . Sebastian Brandt, Manuela Fischer, and Jara Uitto. Matching and MIS for uniformly sparse graphs in the low-memory MPC model. CoRR, abs\/1807.05374, 2018."},{"key":"e_1_3_2_1_28_1","first-page":"40","volume-title":"First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19--21, 2004","author":"Canetti Ran","year":"2004","unstructured":"Ran Canetti , Oded Goldreich , and Shai Halevi . On the random-oracle methodology as applied to length-restricted signature schemes. In Theory of Cryptography , First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19--21, 2004 , Proceedings , pages 40 -- 57 , 2004 . Ran Canetti, Oded Goldreich, and Shai Halevi. On the random-oracle methodology as applied to length-restricted signature schemes. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19--21, 2004, Proceedings, pages 40--57, 2004."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008734"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.74"},{"key":"e_1_3_2_1_34_1","first-page":"649","volume-title":"30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15--19, 2010. Proceedings","author":"De Anindya","year":"2010","unstructured":"Anindya De , Luca Trevisan , and Madhur Tulsiani . Time space tradeoffs for attacks against one-way functions and prgs. In Advances in Cryptology - CRYPTO 2010 , 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15--19, 2010. Proceedings , pages 649 -- 665 , 2010 . Anindya De, Luca Trevisan, and Madhur Tulsiani. Time space tradeoffs for attacks against one-way functions and prgs. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15--19, 2010. Proceedings, pages 649--665, 2010."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020515"},{"key":"e_1_3_2_1_37_1","first-page":"787","volume-title":"International Conference on Machine Learning","author":"Ene Alina","year":"2015","unstructured":"Alina Ene and Huy Nguyen . Random coordinate descent methods for minimizing decomposable submodular functions . In International Conference on Machine Learning , pages 787 -- 795 , 2015 . Alina Ene and Huy Nguyen. Random coordinate descent methods for minimizing decomposable submodular functions. In International Conference on Machine Learning, pages 787--795, 2015."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_10"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48653-5_1"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_42_1","unstructured":"Mohsen Ghaffari Fabian Kuhn and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds.  Mohsen Ghaffari Fabian Kuhn and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds."},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari , Silvio Lattanzi , and Slobodan Mitrovic . Improved parallel algorithms for density-based network clustering . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019 , Long Beach, California, USA, pages 2201--2210 , 2019. Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. Improved parallel algorithms for density-based network clustering. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019, Long Beach, California, USA, pages 2201--2210, 2019."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_1_45_1","first-page":"102","volume-title":"44th Symposium on Foundations of Computer Science, FOCS 2003, 11--14 October 2003, Cambridge, MA, USA","author":"Goldwasser Shafi","year":"2003","unstructured":"Shafi Goldwasser and Yael Tauman Kalai . On the (in)security of the fiat-shamir paradigm . In 44th Symposium on Foundations of Computer Science, FOCS 2003, 11--14 October 2003, Cambridge, MA, USA , Proceedings , pages 102 -- 113 , 2003 . Shafi Goldwasser and Yael Tauman Kalai. On the (in)security of the fiat-shamir paradigm. In 44th Symposium on Foundations of Computer Science, FOCS 2003, 11--14 October 2003, Cambridge, MA, USA, Proceedings, pages 102--113, 2003."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2809814"},{"key":"e_1_3_2_1_49_1","volume-title":"Connected components at scale via local contractions. CoRR, abs\/1807.10727","author":"\u00b8cki Jakub","year":"2018","unstructured":"Jakub ?a \u00b8cki , Vahab S. Mirrokni , and Michal Wlodarczyk . Connected components at scale via local contractions. CoRR, abs\/1807.10727 , 2018 . Jakub ?a\u00b8cki, Vahab S. Mirrokni, and Michal Wlodarczyk. Connected components at scale via local contractions. CoRR, abs\/1807.10727, 2018."},{"key":"e_1_3_2_1_50_1","volume-title":"there is an oblivious RAM lower bound! Electronic Colloquium on Computational Complexity (ECCC), 25:109","author":"Larsen Kasper Green","year":"2018","unstructured":"Kasper Green Larsen and Jesper Buus Nielsen . Yes , there is an oblivious RAM lower bound! Electronic Colloquium on Computational Complexity (ECCC), 25:109 , 2018 . Kasper Green Larsen and Jesper Buus Nielsen. Yes, there is an oblivious RAM lower bound! Electronic Colloquium on Computational Complexity (ECCC), 25:109, 2018."},{"key":"e_1_3_2_1_51_1","first-page":"85","volume-title":"SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4--6, 2011 (Co-located with FCRC 2011)","author":"Lattanzi Silvio","year":"2011","unstructured":"Silvio Lattanzi , Benjamin Moseley , Siddharth Suri , and Sergei Vassilvitskii . Filtering : a method for solving graph problems in mapreduce . In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4--6, 2011 (Co-located with FCRC 2011) , pages 85 -- 94 , 2011 . Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4--6, 2011 (Co-located with FCRC 2011), pages 85--94, 2011."},{"key":"e_1_3_2_1_52_1","first-page":"39","volume-title":"Proceedings","author":"Mahmoody Mohammad","year":"2011","unstructured":"Mohammad Mahmoody , Tal Moran , and Salil P. Vadhan . Time-lock puzzles in the random oracle model. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14--18, 2011 . Proceedings , pages 39 -- 50 , 2011 . Mohammad Mahmoody, Tal Moran, and Salil P. Vadhan. Time-lock puzzles in the random oracle model. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14--18, 2011. Proceedings, pages 39--50, 2011."},{"key":"e_1_3_2_1_53_1","first-page":"21","volume-title":"First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19--21, 2004","author":"Maurer Ueli M.","year":"2004","unstructured":"Ueli M. Maurer , Renato Renner , and Clemens Holenstein . Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In Theory of Cryptography , First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19--21, 2004 , Proceedings , pages 21 -- 39 , 2004 . Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19--21, 2004, Proceedings, pages 21--39, 2004."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90225-K"},{"key":"e_1_3_2_1_55_1","first-page":"153","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015","author":"Vahab","year":"2015","unstructured":"Vahab S. Mirrokni and Morteza Zadimoghaddam. Randomized composable coresets for distributed submodular maximization . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , Portland, OR, USA, June 14--17 , 2015 , pages 153 -- 162 , 2015. Vahab S. Mirrokni and Morteza Zadimoghaddam. Randomized composable coresets for distributed submodular maximization. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14--17, 2015, pages 153--162, 2015."},{"key":"e_1_3_2_1_56_1","first-page":"2049","volume-title":"Advances in Neural Information Processing Systems","author":"Mirzasoleiman Baharan","year":"2013","unstructured":"Baharan Mirzasoleiman , Amin Karbasi , Rik Sarkar , and Andreas Krause . Distributed submodular maximization: Identifying representative elements in massive data . In Advances in Neural Information Processing Systems , pages 2049 -- 2057 , 2013 . Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems, pages 2049--2057, 2013."},{"key":"e_1_3_2_1_57_1","volume-title":"23rd International Conference on Principles of Distributed Systems, OPODIS 2019","author":"Nanongkai Danupon","year":"2019","unstructured":"Danupon Nanongkai and Michele Scquizzato . Equivalence classes and conditional hardness in massively parallel computations . In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019 , December 17 --19 , 2019 , Neuch\u00e2tel, Switzerland, 2019. Danupon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17--19, 2019, Neuch\u00e2tel, Switzerland, 2019."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45708-9_8"},{"key":"e_1_3_2_1_59_1","volume-title":"Round compression for parallel graph algorithms in strongly sublinear space. CoRR, abs\/1807.08745","author":"Onak Krzysztof","year":"2018","unstructured":"Krzysztof Onak . Round compression for parallel graph algorithms in strongly sublinear space. CoRR, abs\/1807.08745 , 2018 . Krzysztof Onak. Round compression for parallel graph algorithms in strongly sublinear space. CoRR, abs\/1807.08745, 2018."},{"key":"e_1_3_2_1_60_1","first-page":"316","volume-title":"23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17--21, 2003","author":"Pass Rafael","year":"2003","unstructured":"Rafael Pass . On deniability in the common reference string and random oracle model. In Advances in Cryptology - CRYPTO 2003 , 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17--21, 2003 , Proceedings , pages 316 -- 337 , 2003 . Rafael Pass. On deniability in the common reference string and random oracle model. In Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17--21, 2003, Proceedings, pages 316--337, 2003."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304607"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935799"},{"key":"e_1_3_2_1_65_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning","author":"Yaroslavtsev Grigory","year":"2018","unstructured":"Grigory Yaroslavtsev and Adithya Vadapalli . Massively parallel algorithms and hardness for single-linkage clustering under ?p -distances . In Proceedings of the 35th International Conference on Machine Learning , 2018 . Grigory Yaroslavtsev and Adithya Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under ?p -distances. In Proceedings of the 35th International Conference on Machine Learning, 2018."}],"event":{"name":"SPAA '20: 32nd 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","EATCS European Association for Theoretical Computer Science"],"location":"Virtual Event USA","acronym":"SPAA '20"},"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.3400223","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400223","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.3400223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":65,"alternative-id":["10.1145\/3350755.3400223","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400223","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"}}]}}