{"entities":{"Q1209332":{"pageid":1220081,"ns":120,"title":"Item:Q1209332","lastrevid":66353391,"modified":"2026-04-12T09:31:36Z","type":"item","id":"Q1209332","labels":{"en":{"language":"en","value":"A probabilistic algorithm for verifying matrix products using \\(O(n^ 2)\\) time and \\(\\log_ 2n+O(1)\\) random bits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167743"}},"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":"Q1209332$018D3BED-3100-450A-9C6D-10E28B2D2DA0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ce8a47d0c64971031ce31456c28c04429252223f","datavalue":{"value":{"text":"A probabilistic algorithm for verifying matrix products using \\(O(n^ 2)\\) time and \\(\\log_ 2n+O(1)\\) random bits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209332$B2FEAC87-331C-4E7A-B36D-EB66E5458A55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f861a1eca94131b8a2adbcb3202affd4bc07d6a5","datavalue":{"value":"0770.65029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209332$2D40DE3D-2486-4EFD-8F7C-BAAB3F65A49F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"410fe19b4d7677aa7d0741812351af29a4368b8d","datavalue":{"value":"10.1016/0020-0190(93)90224-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209332$F1CD0446-FAAD-4F85-B8F1-6A397BF345EF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a79ff5cc25fb93ea7745f44f97d7b4a79364b665","datavalue":{"value":{"entity-type":"item","numeric-id":880553,"id":"Q880553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$204CEB7A-E03A-4104-B850-1EECC193F73B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"62055d966611cc21fe9df005e85edd1df64f0338","datavalue":{"value":{"entity-type":"item","numeric-id":1209331,"id":"Q1209331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$195F4D83-8072-431B-8EC1-E3688869164C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$BBABC50B-E4B5-4CFC-9F9E-1239F237D225","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1209332$549B5B68-1D74-4E48-9428-27FB559184BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7599908de0898d8e8c4fa602331dbc30cdcfb65f","datavalue":{"value":"The following problem is considered: given three \\(n\\times n\\) matrices \\(A\\), \\(B\\) and \\(C\\), how difficult is it to verify whether \\(AB=C\\)?   Freivalds' probabilistic algorithm to verify matrix products using \\(O(n^ 2)\\) multiplications and additions, and \\(n\\) bits of randomness is known. This algorithm selects a vector \\(v\\) at random from \\(\\{-1,1\\}^ n\\). It then computes the products \\(A(Bv)\\) and \\(Cv\\), and accepts (reports that \\(AB\\neq C\\)) if and only if \\(ABv\\neq Cv\\).   A similar method is proposed in this paper, but the vector \\(v\\) is chosen from a set of less than \\(4n\\) vectors, requiring only \\(\\lceil log_ 2n\\rceil+1\\) random bits. In section 2 the simplest version of the algorithm for integer matrices is presented. Section 3 shows how to improve the bit complexity. Section 4 extends the algorithm to matrices over finite fields and Section 5 shows how to reduce the error probability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209332$C311BDDA-77A9-4ED9-865D-0B5D8D8FDAAE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209332$AC04147E-9AD3-466F-BFF0-3E7B2160B4CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209332$0B4EF5C2-9020-4771-9E43-114628E40777","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"330b1207a5afb4d82a04cf656df591dd2462e46d","datavalue":{"value":"167743","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209332$6EB11AF3-9D87-45AD-9737-F09AE7557120","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1bd7465da93426ea77250e10d8333e8ed59b611","datavalue":{"value":"design of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209332$A0102202-5DD0-4CED-A168-2714DE0F5CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61dc0d24c2f9fed588cdf026ed25c93734181934","datavalue":{"value":"Freivalds' probabilistic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209332$EF8E8168-A8BD-4B77-8CC9-8D9F1553DF60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2349c47da5a02e786015e845c43c849e7582d0c8","datavalue":{"value":"matrix products","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209332$E77F6BDD-89F1-4CB4-BA97-F5048B95943A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0df094ce3faeec3bf0d6f63dfdd884491bce6fd1","datavalue":{"value":"bit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209332$7FC50958-31C4-4599-A645-836E0BB0E3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6deca9b5ebc941b9361ce3a1c641ad2e809f90e6","datavalue":{"value":"error probability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209332$D00BDE03-6851-4B16-9D46-AAA10976D2B5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"134806dc1ba0797ec6ff5be489fb4d452d899e3c","datavalue":{"value":{"entity-type":"item","numeric-id":1031570,"id":"Q1031570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$A92B2CF7-5B26-4D6A-B307-D679ED4607F0","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":"Q1209332$08A2E58C-62E4-4CE3-99EA-3492B56B9F58","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4160581d4aaefdde616ac4c6be9092fc18e64d0f","datavalue":{"value":{"entity-type":"item","numeric-id":4195937,"id":"Q4195937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$73AD42CE-1AA1-477A-8E38-09582D484DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e28d865b6a527d6aef184a58e15bb15ad21dc2c","datavalue":{"value":{"entity-type":"item","numeric-id":3856819,"id":"Q3856819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$EC406441-359D-429D-970B-81AD9ACED961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95345f69dfeae4be53e3f6612576bcc12e7cba27","datavalue":{"value":{"entity-type":"item","numeric-id":3919787,"id":"Q3919787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$6A9673B2-3FE9-4320-A9C6-73CD1D2DE119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46ccba14837ab6c5bc350f0628d92fafda2a68c8","datavalue":{"value":{"entity-type":"item","numeric-id":3902523,"id":"Q3902523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209332$C0C085E1-0D55-4EC1-8597-6DB1A9A5EAA9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"85bc5a307712a8ee29a95caae9ce7a85dfef4037","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90224-w","type":"string"},"datatype":"url"},"type":"statement","id":"Q1209332$AB7BDBFB-BBD6-439B-93BE-A6C12A330EF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2c662d0e4d0a892c844bd4bb92dc623726313e36","datavalue":{"value":"W2051391952","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209332$43DC1C38-3CA7-4F7E-8FB3-905FE34851E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"899fbce6f56f3117022409fc6364becf4e13a9df","datavalue":{"value":{"entity-type":"item","numeric-id":1313769,"id":"Q1313769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"551cce2d6e51164047e10b43c2610482646c39c8","datavalue":{"value":{"amount":"+0.8406921029090881","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":"Q1209332$F95D96FC-A392-4415-B4DA-93439FB3EDA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4633aa06e6ac00edf78e20fbeb7b341a1d7768fe","datavalue":{"value":{"entity-type":"item","numeric-id":2938115,"id":"Q2938115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a621765aa186feeb1303fac018d0545be18a8c7a","datavalue":{"value":{"amount":"+0.812972903251648","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":"Q1209332$F93A3F6B-AD5D-4E26-BCBB-9C51BC2E7E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d23072c230c5693be1c2669942d4a5eaa1c84e5a","datavalue":{"value":{"entity-type":"item","numeric-id":2026637,"id":"Q2026637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca57db79faaa7a05d9279e99fd789d283951b750","datavalue":{"value":{"amount":"+0.8063610792160034","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":"Q1209332$D3BA9AEB-F69D-4722-9639-4B1466937C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deba273b3e79ad84bc7e5db62b39dea89dc41bc2","datavalue":{"value":{"entity-type":"item","numeric-id":3190156,"id":"Q3190156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16c8cfcad0746ef43e6d4bd08ce409b43dbd0601","datavalue":{"value":{"amount":"+0.7985824346542358","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":"Q1209332$9B291C52-E4AF-417A-9116-E65F40B703FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8ee4644ba116772c84080a7f89570419d9e7369","datavalue":{"value":{"entity-type":"item","numeric-id":3477964,"id":"Q3477964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"298372fde0aeb1acdb481f50c1b5c65da0171a25","datavalue":{"value":{"amount":"+0.78718501329422","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":"Q1209332$A9D5DCE9-37C3-4175-AD8D-39EECBB683DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A probabilistic algorithm for verifying matrix products using \\(O(n^ 2)\\) time and \\(\\log 2n+O(1)\\) random bits","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_probabilistic_algorithm_for_verifying_matrix_products_using_%5C(O(n%5E_2)%5C)_time_and_%5C(%5Clog_2n%2BO(1)%5C)_random_bits"}}}}}