{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:50Z","timestamp":1777954610643,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":89,"publisher":"ACM","funder":[{"name":"European Research Council (ERC) under the European Union?s Horizon 2020 research and innovation programme","award":["818252,101113120, 101138056"],"award-info":[{"award-number":["818252,101113120, 101138056"]}]},{"DOI":"10.13039\/501100006374","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1354\/23, 514\/20"],"award-info":[{"award-number":["1354\/23, 514\/20"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science Accelerator"},{"name":"Frontiers in Science initiative of the Ministry of Innovation, Science and Technology"},{"name":"Len Blavatnik and the Blavatnik Family Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743307","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"514-524","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimizing Processor Count for Fault Tolerant Toom-Cook Algorithms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-5762-9917","authenticated-orcid":false,"given":"Roy","family":"Nissim","sequence":"first","affiliation":[{"name":"The Hebrew University of Jerusalem, Department of Computer Science, Jerusalem, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1309-5566","authenticated-orcid":false,"given":"Oded","family":"Schwartz","sequence":"additional","affiliation":[{"name":"The Hebrew University of Jerusalem, Department of Computer Science, Jerusalem, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0879-2457","authenticated-orcid":false,"given":"Yuval","family":"Spiizer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Department of Computer Science, Tel Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)","author":"Ananthanarayanan Ganesh","year":"2013","unstructured":"Ganesh Ananthanarayanan, Ali Ghodsi, Scott Shenker, and Ion Stoica. 2013. Effective straggler mitigation: Attack of the clones. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 185--198."},{"key":"e_1_3_2_1_2_1","volume-title":"9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10)","author":"Ananthanarayanan Ganesh","year":"2010","unstructured":"Ganesh Ananthanarayanan, Srikanth Kandula, Albert Greenberg, Ion Stoica, Yi Lu, Bikas Saha, and Edward Harris. 2010. Reining in the outliers in {Map-Reduce} clusters using mantri. In 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2004.2"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312044"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2020.i2.222-244"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310558"},{"key":"e_1_3_2_1_8_1","volume-title":"Fault Tolerance with High Performance for Fast Matrix Multiplication. In 2020 Proceedings of the SIAM Workshop on Combinatorial Scientific Computing. SIAM, 106--117","author":"Birnbaum Noam","year":"2020","unstructured":"Noam Birnbaum, Roy Nissim, and Oded Schwartz. 2020. Fault Tolerance with High Performance for Fast Matrix Multiplication. In 2020 Proceedings of the SIAM Workshop on Combinatorial Scientific Computing. SIAM, 106--117."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975215.3"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975215.3"},{"key":"e_1_3_2_1_11_1","volume-title":"What about Toom-Cook matrices optimality. Centro \"Vito Volterra\" Universit\u00e0 di Roma Tor Vergata","author":"Bodrato Marco","year":"2006","unstructured":"Marco Bodrato and Alberto Zanoni. 2006. What about Toom-Cook matrices optimality. Centro \"Vito Volterra\" Universit\u00e0 di Roma Tor Vergata (2006)."},{"key":"e_1_3_2_1_12_1","volume-title":"Toward exascale resilience: 2014 update. Supercomputing frontiers and innovations 1, 1","author":"Cappello Franck","year":"2014","unstructured":"Franck Cappello, Al Geist, William Gropp, Sanjay Kale, Bill Kramer, and Marc Snir. 2014. Toward exascale resilience: 2014 update. Supercomputing frontiers and innovations 1, 1 (2014), 5--28."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10723-007-9068-6"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. IEEE, 10-pp.","author":"Chen Zizhong","year":"2006","unstructured":"Zizhong Chen and Jack Dongarra. 2006. Algorithm-based checkpoint-free fault tolerance for parallel matrix computations on volatile resources. In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. IEEE, 10-pp."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.58"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0249212-8"},{"key":"e_1_3_2_1_17_1","volume-title":"Communication-optimal parallel standard and karatsuba integer multiplication in the distributed memory model. arXiv","author":"Stefani Lorenzo De","year":"2020","unstructured":"Lorenzo De Stefani. 2020. Communication-optimal parallel standard and karatsuba integer multiplication in the distributed memory model. arXiv (2020)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538551"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_20_1","volume-title":"IEEE 27th International Symposium on. IEEE","author":"Demmel James","year":"2013","unstructured":"James Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Benjamin Lipshitz, Oded Schwartz, and Omer Spillinger. 2013. Communication-optimal parallel recursive rectangular matrix multiplication. Parallel and Distributed Processing (IPDPS), IEEE 27th International Symposium on. IEEE (2013), 261--272."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2018.2878598"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.98.012311"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2927558"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2929328"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2004.15"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09526-8_5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070711761"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745873"},{"key":"e_1_3_2_1_29_1","volume-title":"GNU MP: The GNU multiple precision arithmetic library","author":"Granlund Torbj\u00f6rn","year":"2004","unstructured":"Torbj\u00f6rn Granlund. 2004. GNU MP: The GNU multiple precision arithmetic library. http:\/\/gmplib.org\/ (2004)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178249"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2018.2886962"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2001.941390"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2021.193.2.4"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"4327","author":"Hong Sangwoo","year":"2021","unstructured":"Sangwoo Hong, Heecheol Yang, Youngseok Yoon, Taehyun Cho, and Jungwoo Lee. 2021. Chebyshev Polynomial Codes: Task Entanglement-based Coding for Distributed Matrix Multiplication. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 4319--4327."},{"key":"e_1_3_2_1_35_1","volume-title":"Abraham","author":"Huang Kuang H.","year":"1984","unstructured":"Kuang H. Huang and Jacob A. Abraham. 1984. Algorithm-based fault tolerance for matrix operations. IEEE transactions on computers 100, 6 (1984), 518--528."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6284026"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.140518"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055281"},{"key":"e_1_3_2_1_40_1","first-page":"595","article-title":"Multiplication of MultiDigit Numbers on Automata","volume":"7","author":"Karatsuba Anatoly","year":"1963","unstructured":"Anatoly Karatsuba and Yu Ofman. 1963. Multiplication of MultiDigit Numbers on Automata. Soviet Physics-Doklady 7 (1963), 595--596.","journal-title":"Soviet Physics-Doklady"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/JCN.2017.000075"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1987.232562"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.3390\/app11093752"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2736066"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006962"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006963"},{"key":"e_1_3_2_1_47_1","volume-title":"Reviewers Marco Lewandowsky, and Miha Stopar","author":"Leuven Ku","year":"2020","unstructured":"Ku Leuven, Reviewers Marco Lewandowsky, and Miha Stopar. 2020. D5. 3 Final Report on Hardware-Optimized Schemes. FENTEC (2020)."},{"key":"e_1_3_2_1_48_1","volume-title":"Coded MapReduce. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton). 964--971","author":"Li Songze","year":"2015","unstructured":"Songze Li, Mohammad Ali Maddah-Ali, and A Salman Avestimehr. 2015. Coded MapReduce. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton). 964--971."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2756959"},{"key":"e_1_3_2_1_50_1","volume-title":"Coded TeraSort. In 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 389--398","author":"Li Songze","year":"2017","unstructured":"Songze Li, Sucha Supittayapornpong, Mohammad Ali Maddah-Ali, and Salman Avestimehr. 2017. Coded TeraSort. In 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 389--398."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.33"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/315891.315965"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366706"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3524298"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663171.2663188"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008264"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.01.022"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.49"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.18"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81293-5_13"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977714.12"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659961"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.730527"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2023.3252504"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2904055"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00473-8"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2018.2877391"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342014522573"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2022.3182221"},{"key":"e_1_3_2_1_71_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"5945","author":"Soto Pedro","year":"2019","unstructured":"Pedro Soto, Jun Li, and Xiaodi Fan. 2019. Dual Entangled Polynomial Code: Three-Dimensional Coding for Distributed Matrix Multiplication. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 5937--5945."},{"key":"e_1_3_2_1_72_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"3376","author":"Tandon Rashish","year":"2017","unstructured":"Rashish Tandon, Qi Lei, Alexandros G Dimakis, and Nikos Karampatziakis. 2017. Gradient Coding: Avoiding Stragglers in Distributed Learning. In Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 70). PMLR, 3368--3376."},{"key":"e_1_3_2_1_73_1","first-page":"714","article-title":"The complexity of a scheme of functional elements realizing the multiplication of integers","volume":"3","author":"Toom Andrei L","year":"1963","unstructured":"Andrei L Toom. 1963. The complexity of a scheme of functional elements realizing the multiplication of integers. In Soviet Mathematics Doklady, Vol. 3. 714--716.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535372.2535392"},{"key":"e_1_3_2_1_76_1","volume-title":"Efficient Task Replication for Fast Response Times in Parallel Computation. In The 2014 ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '14)","author":"Wang Da","year":"2014","unstructured":"Da Wang, Gauri Joshi, and Gregory Wornell. 2014. Efficient Task Replication for Fast Response Times in Parallel Computation. In The 2014 ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '14). Association for Computing Machinery, 599--600."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847220.2847223"},{"key":"e_1_3_2_1_78_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"5160","author":"Wang Sinong","year":"2018","unstructured":"Sinong Wang, Jiashang Liu, and Ness Shroff. 2018. Coded Sparse Matrix Multiplication. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80). PMLR, 5152--5160."},{"key":"e_1_3_2_1_79_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"5160","author":"Wang Sinong","year":"2018","unstructured":"Sinong Wang, Jiashang Liu, and Ness Shroff. 2018. Coded Sparse Matrix Multiplication. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR, 5152--5160."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/FTCS.1995.466999"},{"key":"e_1_3_2_1_81_1","volume-title":"Dedy Septono Catur Putranto, and Howon Kim","author":"Wardhani Rini Wisnu","year":"2024","unstructured":"Rini Wisnu Wardhani, Dedy Septono Catur Putranto, and Howon Kim. 2024. High-and Half-Degree Quantum Multiplication for Post-Quantum Security Evaluation. IEEE Access (2024)."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCS.1988.12538"},{"key":"e_1_3_2_1_83_1","first-page":"I","article-title":"Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication","volume":"30","author":"Yu Qian","year":"2017","unstructured":"Qian Yu, Mohammad Maddah-Ali, and Salman Avestimehr. 2017. Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication. In Advances in Neural Information Processing Systems 30, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 4403--4413.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_84_1","volume-title":"Advances in Neural Information Processing Systems","author":"Yu Qian","unstructured":"Qian Yu, Mohammad Maddah-Ali, and Salman Avestimehr. 2017. Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc."},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2963864"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2009.23"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837934.1837995"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/ARITH.1993.378084"}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","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 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:20:29Z","timestamp":1777922429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":89,"alternative-id":["10.1145\/3694906.3743307","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743307","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}