{"entities":{"Q1068514":{"pageid":1079266,"ns":120,"title":"Item:Q1068514","lastrevid":66205572,"modified":"2026-04-12T08:15:10Z","type":"item","id":"Q1068514","labels":{"en":{"language":"en","value":"An improved algorithm for Boolean matrix multiplication"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3932299"}},"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":"Q1068514$59CCBD56-29EF-4DAD-8E95-04EBEF7FF580","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f251f8ac541d091433f6c29072913274e04d325","datavalue":{"value":{"text":"An improved algorithm for Boolean matrix multiplication","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068514$8AFBE526-ADDD-408D-8064-5CC50E35632B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d5659a755e0a37099bf14f64296fe3a3daa65732","datavalue":{"value":"0582.65029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068514$0A466266-EE1C-41FF-8B2B-2D08A29909B9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"996e67d1461120bb75814ae72882cc1d80295fd9","datavalue":{"value":"10.1007/BF02240211","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068514$4ADDF05C-8C28-40E7-8885-DA3321D9C2DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db6df3606e104c2161180e2597803fd70c72d072","datavalue":{"value":{"entity-type":"item","numeric-id":557817,"id":"Q557817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068514$39488AA9-59E1-4350-B905-370D3C0AB945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4c9be9ca23a2d959da50f0057a270a7fbc59409","datavalue":{"value":{"entity-type":"item","numeric-id":170450,"id":"Q170450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068514$43B3FD95-2790-4432-98F4-6DA1189741C0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068514$D8C63924-7DF8-46F7-8ED1-C005AF32A72B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1068514$B7C28CDF-0355-45B7-A370-C94B57F08FE0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ca71192650f914a0c56f54ae3a79d263ed41af3f","datavalue":{"value":"A new algorithm for computing the product of two arbitrary \\(N\\times N\\) Boolean matrices is presented. The algorithm requires \\(O(N^ 3/\\log N)\\) bit operations and only O(N log N) bits of additional storage. This represents an improvement on the Four Russians' method which requires the same number of operations but uses \\(O(N^ 3/\\log N)\\) bits of additional storage.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068514$1B08FB59-6FA6-432E-AE19-F52121FB4143","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068514$030A02FD-1F62-4A6D-8C2A-FE4B6A9B0A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068514$39AFDA37-E344-43D2-9263-6D822D5AD55E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03c5069bb74191605ce68e2f2f9c936118b00d95","datavalue":{"value":"3932299","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068514$1DD73FB4-9365-4902-BC61-B8DD4B3582C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aba72f7a50c6331fc87e2da0e7087379a0bbc676","datavalue":{"value":"Boolean matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068514$CDBCB26B-DE81-43BC-9D32-797A4CC47799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068514$8B27E7C8-624F-432C-A523-A736AED0C6A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6514abbab48b1974f84527a1b00adf91c018f503","datavalue":{"value":"Four Russians' method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068514$2BF72E07-5992-4AD6-93F2-02D41D00E8AB","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":"Q1068514$F2E2502E-43D0-42CE-9C99-8D9E74D52193","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a6030b36d8e5c354770b6a8c9a91f5a75bf452e","datavalue":{"value":{"entity-type":"item","numeric-id":761038,"id":"Q761038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068514$DDFF29BE-488A-4F4D-8C97-010B0D878B30","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f395ad9504376ff3ba8cd94c08ed3dc1a5cc4659","datavalue":{"value":"https://doi.org/10.1007/bf02240211","type":"string"},"datatype":"url"},"type":"statement","id":"Q1068514$B23C63BB-8948-4448-8F17-B7150443320A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"25fad3b3ee9795cde419cc66154b809e6a02902e","datavalue":{"value":"W184459568","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068514$7A9F5DDD-5391-4556-8334-2B36415AD606","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74b50468e385e4d9bb82d795d5b2cae8f53a200e","datavalue":{"value":{"entity-type":"item","numeric-id":5258776,"id":"Q5258776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24ddfd45720571d5785ad03e7a476bb16ec4c17e","datavalue":{"value":{"amount":"+0.8717139959335327","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":"Q1068514$6B18125C-1421-4D91-BCC8-05564CE6DB39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b50ad8e1f547f87884bfb7f80d03f9add7f6e4","datavalue":{"value":{"entity-type":"item","numeric-id":5363082,"id":"Q5363082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ef05de11a882a598175d0a8fb8cf47dd44dc551","datavalue":{"value":{"amount":"+0.8455333709716797","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":"Q1068514$53BEA699-C4C6-4876-ABB8-2198FAAEF583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"662e34a1fc9fa5c5e59d19202a867320872d71ad","datavalue":{"value":{"entity-type":"item","numeric-id":3639263,"id":"Q3639263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c513641cb3f5a3857a83d8b83ab02fce90bfb593","datavalue":{"value":{"amount":"+0.8360158205032349","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":"Q1068514$3951371E-BD16-40C3-B789-7D6CEC1A895E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cef9a84a2e72a9d1243779321a218a0866c87fd","datavalue":{"value":{"entity-type":"item","numeric-id":634680,"id":"Q634680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed491df42a43077205f30bc7c5e5e1bb0fef2ca0","datavalue":{"value":{"amount":"+0.8350192308425903","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":"Q1068514$9632C56C-A32E-474B-B6F9-D6274CC865AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a410ef688dd27ff880eb2f291a72733a1b78c4d1","datavalue":{"value":{"entity-type":"item","numeric-id":3454755,"id":"Q3454755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"045be6c45e4f2f7be8e6bc3928facf6918b036ed","datavalue":{"value":{"amount":"+0.8206148147583008","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":"Q1068514$D625142C-0610-4C6E-BBF8-4B9FF382D92C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An improved algorithm for Boolean matrix multiplication","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_improved_algorithm_for_Boolean_matrix_multiplication"}}}}}