{"entities":{"Q2290622":{"pageid":2301365,"ns":120,"title":"Item:Q2290622","lastrevid":73651584,"modified":"2026-04-14T16:47:55Z","type":"item","id":"Q2290622","labels":{"en":{"language":"en","value":"Sparse matrix multiplication and triangle listing in the congested clique model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7159797"}},"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":"Q2290622$C8C2062A-E569-45D8-B9C6-3771B2B90F4C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f6ff63f83cf533755c04d7b5632888ffc3b84c7","datavalue":{"value":{"text":"Sparse matrix multiplication and triangle listing in the congested clique model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2290622$07512AD5-E883-4B65-A48C-718B1AD703B9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09a2fa37f6d8e0e39003b0f1e1fc8df8684d129f","datavalue":{"value":"1447.68015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$4353A76D-9C6E-4024-BEC2-621A022C7B81","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"50169214229f0aaa4dd9bb9948faad51feef1744","datavalue":{"value":{"entity-type":"item","numeric-id":259273,"id":"Q259273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$680946D4-F0CC-4E95-A442-782AB9064F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b8b2ff2a62bfb0168d5df31d2c747dd07d8e505","datavalue":{"value":{"entity-type":"item","numeric-id":2064056,"id":"Q2064056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$B97FEFD1-E5BD-4EBA-9654-41EB2C2DC49C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"509d3b7ae2010334af953a3be6446e2520a4fa3f","datavalue":{"value":{"entity-type":"item","numeric-id":2290621,"id":"Q2290621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$7392E4AD-B94E-4E39-B8C6-1F1C1EB998F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$5371A170-F006-4459-842A-80C8BB5A7108","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"36449951a56e6135e4ec71fa99d76436027843e1","datavalue":{"value":{"time":"+2020-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2290622$776BA3D3-9D78-4B6F-99AA-4DD8A60FA44C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b591bc6b7e374fd0817b4c344e154ff3ac0d2b7","datavalue":{"value":"https://arxiv.org/abs/1802.04789","type":"string"},"datatype":"url"},"type":"statement","id":"Q2290622$794C6098-FC54-4987-87E0-A36462AA9AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed66d8ff7e8ebd0aaca7da342b44928ec7d8c562","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2018/10064/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2290622$8004ADA0-E477-4BEE-B1BD-A8BE613AA3C6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5e6b161785d1413f00de57bd77e7afe3504c54c","datavalue":{"value":"The paper deals with the problem of multiplying sparse matrices. For the parallel setting the distributed Congested Clique model, which consists of nodes in a fully connected synchronous network, is used. A new deterministic algorithm with a round complexity which depends on the sparsity of the input matrices is proposed. A special characteristic of the algorithm is that it speeds up matrix multiplication even if only one of the input matrices is sparse. The approach is extended to obtain a deterministic algorithm for sparsity-aware triangle listing in the Congested Clique model, in which each triangle needs to be known to some node.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290622$31986FF7-46B2-4DAE-B3ED-3A8B424803EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$9C6AEBFF-1549-4D43-87A0-465EE0D4D521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$24FD2A7E-1E3E-4B7E-9B41-500CE0D1ECFD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0691a06b830db1a99ed887b7fe58004d5998566e","datavalue":{"value":"7159797","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$669BB711-73EB-458B-8B6D-1D6E6BB74134","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387e204c6977d7b097ac93bf9a6ecf723e21df10","datavalue":{"value":"distributed algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290622$BB30D86C-0A81-432A-80D8-F4BAC67C73DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a0f8179d822bbb2f8c96a5418344d7d22f05aa9","datavalue":{"value":"congested clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290622$952EF52E-E834-4618-9F60-E595E2B93D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de71a87004b2cb6be9dfb83edd24b279968af4f7","datavalue":{"value":"matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290622$5C4937E6-7317-4B15-99A4-5F7369934154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c395e9daea62c04ec7981da0604fa318d2184d1","datavalue":{"value":"triangle listing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290622$67C2E9A3-7C03-409D-86BD-B2F9E0CFB04A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2f9e16b52bc8c390b9fea0fb31de1975133dd070","datavalue":{"value":{"entity-type":"item","numeric-id":455938,"id":"Q455938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$F772B5DE-2FCF-49E5-A76C-6B761EE93FD7","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":"Q2290622$DE8EA080-2BDA-4CF5-BA18-F95E23C1BF5C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e8b6cc09f77590132fb597c853461997148100c0","datavalue":{"value":"W2988246677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$4A490E1C-1B05-4FCB-B3D0-41303969734B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"246e997ac5be85679ca39a610c5e7ac50170cbb8","datavalue":{"value":{"entity-type":"item","numeric-id":675293,"id":"Q675293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$0009B766-974A-462E-914B-34BAA25E5DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64ddcfa45907b9c7af1de0965493975917e31dd4","datavalue":{"value":{"entity-type":"item","numeric-id":2833530,"id":"Q2833530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$20C796CA-3710-4A6F-ADA4-6DF068320E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4015db1aec16b2d4ea9a6bb21cd8bb17a0c1272","datavalue":{"value":{"entity-type":"item","numeric-id":3165441,"id":"Q3165441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$A1B78B02-A8A5-4128-B7A6-C0C0D96FF456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480ac560f713e57a5ee8cd072f59d2635f9c43d4","datavalue":{"value":{"entity-type":"item","numeric-id":915378,"id":"Q915378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$50A066D7-E22D-41D7-8DAF-CFE2B0D0286C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13b2c69d9c98737c488eab78267074b70ad58ca4","datavalue":{"value":{"entity-type":"item","numeric-id":4909412,"id":"Q4909412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$77439DBF-B08B-474F-8C19-CF638E14DD58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c006bffa7e2704666e0e620fcb8a2d2156349b46","datavalue":{"value":{"entity-type":"item","numeric-id":2943637,"id":"Q2943637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$02A294FE-8A9C-4399-80AB-BCB021DC87DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84ed68bb82322138e41236c78cc7522d16decb13","datavalue":{"value":{"entity-type":"item","numeric-id":3452408,"id":"Q3452408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$7A607F5E-AEE7-4988-97C0-4A2D6A00AF0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b457cc6785d2f481574929c226f9679da7db280","datavalue":{"value":{"entity-type":"item","numeric-id":1660920,"id":"Q1660920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$81E23B94-7CD1-4E13-89AE-F0F57D10D696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa7f67ec15e7cdd5e9911ea36e77501a512026f","datavalue":{"value":{"entity-type":"item","numeric-id":4607951,"id":"Q4607951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$103A809E-FE9F-4955-A1C3-A415F468BA3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e9e7c0264e9559bde1ec172cdeef82e0d29eef6","datavalue":{"value":{"entity-type":"item","numeric-id":4164723,"id":"Q4164723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$6964D736-550C-4569-B950-F5567553E39F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f58339fdf4a803812d900d7a65694b3a4a9e996e","datavalue":{"value":{"entity-type":"item","numeric-id":5368990,"id":"Q5368990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$2FF95E1F-B2D8-4037-BCBC-15A3BDFF72F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1c65d8466e00800d16add869af1ce7009df96f2","datavalue":{"value":{"entity-type":"item","numeric-id":3601522,"id":"Q3601522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$4DA87B32-E7DC-4EAE-BC84-AE5778785F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6b974ced6ed09fd7f849526ef047c459995c20e","datavalue":{"value":{"entity-type":"item","numeric-id":5362982,"id":"Q5362982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$0AD3379F-B021-44FB-98C7-AEB9E37EB07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad90aaf9b49512ef25cc7c2138fec5f1935e79af","datavalue":{"value":{"entity-type":"item","numeric-id":5176081,"id":"Q5176081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$C7D2E297-5C6B-4C93-93DA-236B3FEAC26B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"091e61f22fede451c3b7d23bd3ae76524dba441f","datavalue":{"value":{"entity-type":"item","numeric-id":5259592,"id":"Q5259592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$8FDB4078-F808-4E07-9BDB-E3E696D16635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"214b81544365b618891db1c0645b236fa1178703","datavalue":{"value":{"entity-type":"item","numeric-id":5203926,"id":"Q5203926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$33AE8877-35EC-492B-8B40-B3CA04029B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1746c0002a982167f6b872896509d0ce78aa9e","datavalue":{"value":{"entity-type":"item","numeric-id":2536323,"id":"Q2536323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$C40BF4DC-2806-42D8-A3EC-86187EA984D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9a5bd8b3cfeb0d87f3dd9a27e3cf9df7f51dc7e","datavalue":{"value":{"entity-type":"item","numeric-id":4535018,"id":"Q4535018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$C389FC06-81DD-4F8C-89A0-64523EF82E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"997a4e5c6e10f7b5868b2a5d332887ed8bbec1f2","datavalue":{"value":{"entity-type":"item","numeric-id":5415522,"id":"Q5415522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$F849BA35-6C4B-4D23-A845-8881C16BA7C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19f017610d2fd7ccec3b09977ae0122c1cf254d7","datavalue":{"value":{"entity-type":"item","numeric-id":2944486,"id":"Q2944486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290622$11D4DECD-A421-4964-A97A-166EC7DB3EAC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a9912c38036205d184fc5681a4642a23794e8ad3","datavalue":{"value":"Q126823607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$D7759886-5AD3-4953-8A6F-02F673970EFB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d6947ec22d9ecdc883a4d55e457c4b182c148ed2","datavalue":{"value":"10.1016/J.TCS.2019.11.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290622$80BA155D-A077-4FB4-ABA6-72C60C1AA456","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71c60618cc8f5581ced607be4dd378c8ec1dc202","datavalue":{"value":{"entity-type":"item","numeric-id":1660920,"id":"Q1660920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9d3fbf6e49f73d9942177be7c486e74798295ab","datavalue":{"value":{"amount":"+0.8052994012832642","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2290622$7D7677D9-9194-4763-BB34-EE7238DF64DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c2b751f9401ec08a5013a0e693153b61398f12f","datavalue":{"value":{"entity-type":"item","numeric-id":2943637,"id":"Q2943637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a91ad45a85bbdf0757c04b15bb52a2d7042bc71","datavalue":{"value":{"amount":"+0.7823100686073303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2290622$579A2670-AEC9-420C-9B09-050B381E0F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efdc3fe5b3023c737c925361ea24b43fef75a320","datavalue":{"value":{"entity-type":"item","numeric-id":5368990,"id":"Q5368990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8814c88598d0587db23040299c9e69a7257c94e7","datavalue":{"value":{"amount":"+0.7802937030792236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2290622$71BE5B09-A940-48BB-8084-57024CDA5A08","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sparse matrix multiplication and triangle listing in the congested clique model","badges":[]}}}}}