{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T18:44:18Z","timestamp":1783536258608,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:00:00Z","timestamp":1783296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"H2020 European Research Council award number","award":["810367"],"award-info":[{"award-number":["810367"]}]},{"name":"Advanced Scientific Computing Research award number","award":["DE-SC-0023296"],"award-info":[{"award-number":["DE-SC-0023296"]}]},{"name":"Advanced Scientific Computing Research award number","award":["DE-SC0025394"],"award-info":[{"award-number":["DE-SC0025394"]}]},{"name":"National Science Foundation","award":["CCF-1942892"],"award-info":[{"award-number":["CCF-1942892"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3816782.3819223","type":"proceedings-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:28:33Z","timestamp":1783531713000},"page":"537-549","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9355-4042","authenticated-orcid":false,"given":"Hussam","family":"Al Daas","sequence":"first","affiliation":[{"name":"Rutherford Appleton Laboratory, Didcot, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1557-8027","authenticated-orcid":false,"given":"Grey","family":"Ballard","sequence":"additional","affiliation":[{"name":"Wake Forest University, Winston-Salem, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5880-1076","authenticated-orcid":false,"given":"Laura","family":"Grigori","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9768-0564","authenticated-orcid":false,"given":"Md Taufique","family":"Hussain","sequence":"additional","affiliation":[{"name":"Wake Forest University, Winston-Salem, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1449-0165","authenticated-orcid":false,"given":"Suraj","family":"Kumar","sequence":"additional","affiliation":[{"name":"INRIA Lyon, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5355-482X","authenticated-orcid":false,"given":"Mohammad Marufur","family":"Rahman","sequence":"additional","affiliation":[{"name":"Wake Forest University, Winston-Salem, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4045-0423","authenticated-orcid":false,"given":"Kathryn","family":"Rouse","sequence":"additional","affiliation":[{"name":"Inmar Intelligence, Winston-Salem, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"A. Aggarwal A. K. Chandra and M. Snir. 1990. Communication Complexity of PRAMs. Theor. Comp. Sci. 71 1 (1990). 10.1016\/0304-3975(90)90188-N","DOI":"10.1016\/0304-3975(90)90188-N"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS54959.2023.00044"},{"key":"e_1_3_2_1_3_1","volume-title":"Technical Report RR-9482. Inria Bordeaux-Sud Ouest","author":"Agullo Emmanuel","year":"2022","unstructured":"Emmanuel Agullo, Olivier Coulaud, Alexandre Denis, Mathieu Faverge, Alain Franc, Jean-Marc Frigerio, Nathalie Furmento, Adrien Guilbaud, Emmanuel Jeannot, Romain Peressoni, et al. 2022. Task-based randomized singular value decomposition and multidimensional scaling. Technical Report RR-9482. Inria Bordeaux-Sud Ouest; Inrae-BioGeCo. https:\/\/inria.hal.science\/hal-03773985v2"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538552"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"1576","author":"Balabanov Oleg","year":"2023","unstructured":"Oleg Balabanov, Matthias Beaup\u00e8re, Laura Grigori, and Victor Lederer. 2023. Block Subsampled Randomized Hadamard Transform for Nystr\u00f6m Approximation on Distributed Architectures. In Proceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202). PMLR, 1564\u20131576. https:\/\/proceedings.mlr.press\/v202\/balabanov23a.html"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M138870X"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00065"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","unstructured":"G. Ballard and K. Rouse. 2020. General Memory-Independent Lower Bound for MTTKRP. In SIAM PP. 1\u201311. 10.1137\/1.9781611976137.1","DOI":"10.1137\/1.9781611976137.1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press. https:\/\/web.stanford.edu\/~boyd\/cvxbook\/","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.642949"},{"key":"e_1_3_2_1_11_1","unstructured":"Alberto Bucci Yuji Nakatsukasa and Taejun Park. 2025. Numerical Stability of the Nystr\u00f6m Method. arXiv:2511.15583 [math.NA] https:\/\/arxiv.org\/abs\/2511.15583"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1206"},{"key":"e_1_3_2_1_13_1","unstructured":"Tyler Chen Pradeep Niroula Archan Ray Pragna Subrahmanya Marco Pistoia and Niraj Kumar. 2025. GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches. arXiv:2506.03070 [cs.DS] https:\/\/arxiv.org\/abs\/2506.03070"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Michael Christ James Demmel Nicholas Knight Thomas Scanlon and Katherine A. Yelick. 2013. Communication Lower Bounds and Optimal Algorithms for Programs That Reference Arrays - Part 1. Technical Report UCB\/EECS-2013-61. EECS Department University of California Berkeley. http:\/\/www2.eecs.berkeley.edu\/Pubs\/TechRpts\/2013\/EECS-2013-61.html","DOI":"10.21236\/ADA584726"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/24M1719189"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/24M164063X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Alain Franc Jean-Marc Frigerio Emilie Chancerel Franck Salin Sylvie Th\u00e9rond Fr\u00e9d\u00e9ric Rimet and Agn\u00e8s Bouchez. 2023. Reads and pairwise distances from 10 samples of diatoms in Geneva lake. 10.57745\/NKTRHO","DOI":"10.57745\/NKTRHO"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1466244"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356223"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3007070"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3731599.3767544"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"e_1_3_2_1_24_1","unstructured":"Alex Krizhevsky. 2009. Learning Multiple Layers of Features from Tiny Images. Technical Report. Computer Science Department University of Toronto. https:\/\/www.cs.toronto.edu\/~kriz\/learning-features-2009-TR.pdf"},{"key":"e_1_3_2_1_25_1","first-page":"1","article-title":"Optimal Convergence Rates for Distributed Nystroem Approximation","volume":"24","author":"Li Jian","year":"2023","unstructured":"Jian Li, Yong Liu, and Weiping Wang. 2023. Optimal Convergence Rates for Distributed Nystroem Approximation. Journal of Machine Learning Research 24, 141 (2023), 1\u201339. http:\/\/jmlr.org\/papers\/v24\/21-1049.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS57955.2024.00014"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"L. H. Loomis and H. Whitney. 1949. An Inequality Related to the Isoperimetric Inequality. Bull. Amer. Math. Soc. 55 10 (1949). 10.1090\/S0002-9904-1949-09320-5","DOI":"10.1090\/S0002-9904-1949-09320-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Evert J Nystr\u00f6m. 1930. \u00dcber die praktisch aufl\u00f6sung von integralgleichungen mit anwendungen auf randwertaufgaben. (1930). 10.1007\/BF02547521","DOI":"10.1007\/BF02547521"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/24M1660346"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063405"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2567761"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342005051521"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3008751.3008847"}],"event":{"name":"SPAA '26: 38th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Royal Holloway, University of London London United Kingdom","acronym":"SPAA '26","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture","SIGACT ACM Special Interest Group on Algorithms and Computation Theory","EATCS"]},"container-title":["Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819223","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:29:58Z","timestamp":1783531798000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3816782.3819223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,6]]},"references-count":34,"alternative-id":["10.1145\/3816782.3819223","10.1145\/3816782"],"URL":"https:\/\/doi.org\/10.1145\/3816782.3819223","relation":{},"subject":[],"published":{"date-parts":[[2026,7,6]]},"assertion":[{"value":"2026-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}