{"entities":{"Q1103402":{"pageid":1114154,"ns":120,"title":"Item:Q1103402","lastrevid":42878157,"modified":"2025-07-15T15:50:49Z","type":"item","id":"Q1103402","labels":{"en":{"language":"en","value":"Optimal parallel randomized algorithms for sparse addition and identification"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4053024"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$B90EF1BC-3243-4E16-A691-C7D8CD04430E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40622df6a174158faefe1a1e340f3363cd071da8","datavalue":{"value":{"text":"Optimal parallel randomized algorithms for sparse addition and identification","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103402$E2B245CD-CA5E-4E65-93C0-7ED4BCA6CE79","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2350862e8b3a4fb2a1bcb915780cebb4aa25e895","datavalue":{"value":"0645.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103402$007C6385-B952-48F3-A605-031E4F044706","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c99f8c70d11db3c0660bb644de9b277f73bb4c41","datavalue":{"value":"10.1016/0890-5401(88)90039-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103402$E03A800E-B47A-4B79-A054-4E7D303CC0E8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$06CBE3DB-464C-49BE-8D99-92B5DFCF4BC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1103402$8D18F97A-8ED1-496A-AB2E-FFDB87082F3C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b6f1adeb8da98a34d8db3233a6860daabb822db","datavalue":{"value":"Although many sophisticated parallel algorithms now exist, most of them are not sensitive to properties of the input which can be determined only at run-time. For example, in the case of parallel addition in shared memory models, we intuitively understand that we should not add those inputs whose value is zero. A technique which exploits this idea may beat the general lower bound for addition if the count of nonzero operants is much smaller than the numbers to be added.    In this paper, we device such algorithms for two fundamental problems of parallel computation. Our model of computation is the CRCW PRAM. We first provide a randomized algorithm for parallel addition which never errs and computes the result in O(log m) expected parallel time, where m is the count of nonzero entries among the n numbers to be added. This algorithm uses O(m) shared space. We then use this result to solve an interesting problem of processor identification. All our techniques enjoy the following properties:    (1) They never produce an erroneous answer.    (2) If T is the actual parallel time and E(T) its expected value, then \\(\\Pr ob\\{T>k\\cdot E(T)\\}\\leq n^{-c}\\), where k is arbitrary and \\(c>1\\) is linear on k and can be specified by the implementor of the algorithm.    (3) Our algorithms do not know m initially, but they produce an accurate estimate for it.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103402$AB4D25A4-16C8-4132-A559-3D0595B0BE33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103402$05873355-D0AA-47F3-B720-E94A4BA4387B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103402$660541F5-3A74-4519-BEA8-B73037AD2EFE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"948116f7f18e237223ba3207eb0a6bd9c26211a9","datavalue":{"value":"4053024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103402$37563D6C-1508-4AA2-8ECD-B9D2B9991FF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103402$B8E0FDDA-FAF8-4681-827C-75DD68A700CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1be5035bbaefc18f23cb47009b02596a51f85005","datavalue":{"value":"model of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103402$4A800C0F-41BB-4271-86A8-1D6CB2FD736B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0460a0356485c287af14e0288dac62f7c6b389e4","datavalue":{"value":"CRCW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103402$C702DD42-EDB0-4E22-92AA-18BAF85F18DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f40bfae76b4349217a99a8a0f7c2cc76d7b62e6b","datavalue":{"value":"randomized algorithm for parallel addition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103402$A59D0968-640A-4B4D-A81E-F9668617209F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ed72ab4c470b930d3449c4a0a471ae9bb3ee1a","datavalue":{"value":"processor identification","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103402$CAAB1039-937E-4C20-87B6-7042A47FC951","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8112a4884ac488e222bb031fe5d75202a7b6dcb","datavalue":{"value":{"entity-type":"item","numeric-id":389952,"id":"Q389952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$231B3BA6-4DBF-4BAE-BD98-6E0A6C67C58B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$EE704164-753E-49BD-BC7F-99C7391D7917","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"79214a76593ce90a840de13e00f5aa852a122d39","datavalue":{"value":"https://doi.org/10.1016/0890-5401(88)90039-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1103402$17A65839-EC2E-4AE1-A997-59AE88471E61","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"90b9435ac046fb1d9dde375d69cafdff40249e1d","datavalue":{"value":"W1988308630","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103402$72B4A7A9-7692-423C-93C1-966A53FED0EB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"79ec821f142980120f8086fa3b2990e8d99dfbb8","datavalue":{"value":{"entity-type":"item","numeric-id":4773670,"id":"Q4773670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$5F2D6E9B-E8F7-4F24-AA64-1E337F1BA0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$0D808E0F-0EF0-4025-AAD2-226B03DC5B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d53db4e61bfa2d597f0a53da172502701ac0503","datavalue":{"value":{"entity-type":"item","numeric-id":5402545,"id":"Q5402545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$16096F74-A304-41FB-A727-3AE34BD58DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da11445b9029abd3a57a23edb82501d7b7973625","datavalue":{"value":{"entity-type":"item","numeric-id":799371,"id":"Q799371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$70D04252-0875-48C3-917E-DE4ABA3248E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e472e71486639d0030dd63f9880bf07574170e62","datavalue":{"value":{"entity-type":"item","numeric-id":3769977,"id":"Q3769977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$5B22309E-219F-41D7-9311-5EA632551058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d86254fdb6d475affd1a3d53655f03856dd4f249","datavalue":{"value":{"entity-type":"item","numeric-id":3945587,"id":"Q3945587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103402$E35B7030-FCB0-4410-BA0F-43A4A849305A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"799214a921562c72a620c3997f4654fc4c6c4a31","datavalue":{"value":{"entity-type":"item","numeric-id":3742711,"id":"Q3742711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd1348d00f4c00ed4f0f25a72ec2379c58d90133","datavalue":{"value":{"amount":"+0.9345695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$83FC9A68-738B-4E1B-A831-E666A779B73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a3e553baef38fb335721d148fd7c5559c3515d2","datavalue":{"value":{"entity-type":"item","numeric-id":3975666,"id":"Q3975666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b5e4cd1b07d4dfc5b620d5fd40f044b99a33156","datavalue":{"value":{"amount":"+0.87352276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$DCD40152-44AE-44A4-99A3-4AB837E3256B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2e8fc246eee1c0340800eaf2024c88a9e7ca064","datavalue":{"value":{"entity-type":"item","numeric-id":5750331,"id":"Q5750331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e0e2745ffc0c3efc514d3c9f64b6e29e5ee3260","datavalue":{"value":{"amount":"+0.8725509","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$25CB9AB5-B138-4ED1-AE21-8169F8167765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"145846469931c378cd9365fd9b25ffb4560615e7","datavalue":{"value":{"entity-type":"item","numeric-id":3981404,"id":"Q3981404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e0e2745ffc0c3efc514d3c9f64b6e29e5ee3260","datavalue":{"value":{"amount":"+0.8725509","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$460D6014-D342-460D-B5B7-A801D6833ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db3de95dd070b8e9972be470b6c0f7724ce7a45d","datavalue":{"value":{"entity-type":"item","numeric-id":916307,"id":"Q916307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44350036373774d429b1a122e795e56eb1b17a1b","datavalue":{"value":{"amount":"+0.8698131","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$BEF0E75C-7623-4FF2-8FB2-247B5AB97EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b40a1c166a230651c76689a1e93f04f37659feff","datavalue":{"value":{"entity-type":"item","numeric-id":4247467,"id":"Q4247467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2459707854b0aec2d700fce31d31ee5225425d4e","datavalue":{"value":{"amount":"+0.8652309","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$A0C33BB9-CDD0-4819-92DF-476467D86513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2cc2916e8f9db1318cbad26b3cad015d4deeed2","datavalue":{"value":{"entity-type":"item","numeric-id":4028098,"id":"Q4028098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d13f7653b4608323d48634bbddcf6235e506cdc","datavalue":{"value":{"amount":"+0.8637686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$12D2DEE8-8813-4420-91E7-A8948BC01477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5220b16a2bcd690405ddcf624031fdd241e40d8e","datavalue":{"value":{"entity-type":"item","numeric-id":4394583,"id":"Q4394583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3edd329aa7bb356e9409991c18f4a00a5cfb12c","datavalue":{"value":{"amount":"+0.86116326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$CD35BB65-043C-46EE-80E2-5846A964BABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93017ba581a54a5ebe35e069fdd72776b1c81f07","datavalue":{"value":{"entity-type":"item","numeric-id":3391206,"id":"Q3391206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd7203cdbc4d93e5380138f9618c9086d91eb8ae","datavalue":{"value":{"amount":"+0.86091447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$082FCE52-97F9-4A86-9280-4BAE32620351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"773a199aa23294b6d9cee8fa3b3971bef4d4540c","datavalue":{"value":{"entity-type":"item","numeric-id":2768030,"id":"Q2768030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8cdacaf693a590e128c0a418c3c2b9dcc5b6e1","datavalue":{"value":{"amount":"+0.8582666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1103402$A7DC7DFF-2513-4FDC-A64A-DE4FEF45FC54","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1103402","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1103402"}}}}}