{"entities":{"Q5917579":{"pageid":8034695,"ns":120,"title":"Item:Q5917579","lastrevid":48377038,"modified":"2026-01-04T13:12:40Z","type":"item","id":"Q5917579","labels":{"en":{"language":"en","value":"Clifford algebras and approximating the permanent"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2116456"}},"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":"Q5917579$F28C7A06-62C6-4783-B7EF-3013BCEB56B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d92990139dbd94669cd3e5b5321f5e48adf6267e","datavalue":{"value":{"text":"Clifford algebras and approximating the permanent","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5917579$66D99D39-2AEF-4FBC-9FF4-80111577E7E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d44c5dd708cc9faf460ac0278a0ce296e611508","datavalue":{"value":"1066.68160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5917579$E6F75CD6-54C7-4F5E-9156-52834503A647","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51e5d878ab223add97efedba43b91907f082cce3","datavalue":{"value":"10.1016/S0022-0000(03)00010-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5917579$85272605-76CF-429C-B5DF-088373C825A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1417a4bc588343dd5731e330f16405c77f1d83c","datavalue":{"value":{"entity-type":"item","numeric-id":632951,"id":"Q632951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$200E8A27-382D-4E5D-9517-EB1849807782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"236760d4676076ff7abf6c2c151dcb35fde34e5d","datavalue":{"value":{"entity-type":"item","numeric-id":1886455,"id":"Q1886455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$8234A9F4-19C2-469D-BA2F-43C8E7885F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"098d3ff7023f860d2ad4ff4e99a3417308a6d5f9","datavalue":{"value":{"entity-type":"item","numeric-id":287734,"id":"Q287734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$38630181-59E1-46C0-BD94-8FA0175AC890","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$87AC9705-72F9-4B4A-B551-DA54638A0D18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"037fcf95f864ae0e38f5b6894c4f594ea5ca568c","datavalue":{"value":{"time":"+2004-11-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5917579$47BE6320-403D-4D81-B01E-FE8BE97337A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"74f5151de0e05149bda85fbe535fe3e90e68b408","datavalue":{"value":"Computing permanents is a hard problem compared with computing the determinant. Randomized algorithms can yield estimates of predictable precision computable in a faster way. The present paper studies permanents of \\((0,1)\\)-matrices utilizing the fact that \\(\\text{ perm}(A)=E[|\\text{ det}(A)^2|]\\) is an unbiased estimate, where the positive entries of \\(\\text{ det}(A)\\) are chosen with random signs. The quality of the estimate is given by the second moment, or equivalently \\(E[X_A^2]/E[X_A]^2\\), called critical ratio. The quality of the estimate can be improved if the randomization is not restricted to the sign, but if for the positive elements in \\(A\\) one inserts basis elements of Clifford algebras. Examples with complex numbers and quaternions appear in the literature. The main result is that the estimator is bounded from above by the critical ratio \\((1+1/2^{2q})^{n/2}\\) in \\(CL_m\\) with \\(m = 4q+2\\) for \\(n\\times n\\)-matrices. The authors implemented such algorithms showing the improvement. If determinants of Clifford valued matrices can be computed as easily as ordinary determinants, such an algorithm could come up with a polynomial time estimate for permanents.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5917579$2AEE9E18-DD62-472C-877A-806A3050830D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b4f0730d338033f52bcb97fa95e12d43597a7c8d","datavalue":{"value":{"entity-type":"item","numeric-id":178244,"id":"Q178244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$8B1657C5-A8C9-431C-8FA9-C5896A2823DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5917579$914D0B1E-76A3-4C0E-BB5B-E7F4525134A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f35883713e23ca3f0ced48b60a92f4891f4d526","datavalue":{"value":"15A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5917579$D420FF60-0FE7-423B-B4B2-2DEC30C8114E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"29ea8761824317642da881851bf3c32e9600ace3","datavalue":{"value":"2116456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5917579$F839269E-5D1A-4A8D-B6B4-A2481C3C7950","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b91b53d582dd46c42c8a8a6c2058ac8b8b7e622d","datavalue":{"value":"permanents","type":"string"},"datatype":"string"},"type":"statement","id":"Q5917579$98726E5D-CB9E-4965-B40D-5E03EAB91E61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae6ff3c47ae255c50cf9266476f4d21369eaa2b0","datavalue":{"value":"explicit algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5917579$7F344B34-CAC8-40BD-8770-F30009FAA2C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfe38d75be839243791bd9ac0cf0e0dbfae29d1b","datavalue":{"value":"second Clifford algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q5917579$C057A882-9FCB-49D9-AA5C-BF602E451070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6814185f0686788c236256ddbd14f8c18ba3db6","datavalue":{"value":"quaternions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5917579$0A76DC14-03DF-43CA-BD5B-7838DA6EB5F9","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":"Q5917579$D350878F-7386-4726-8077-58955BD00B51","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47794604261fc5b99c3c8d443056e4962050e6e","datavalue":{"value":{"entity-type":"item","numeric-id":4039891,"id":"Q4039891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$D043A142-FFFF-43D1-B83E-7DF91F462A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc5ece43c2deaf0ff72258fd460e49b493be594f","datavalue":{"value":{"entity-type":"item","numeric-id":1361138,"id":"Q1361138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$3A4C0705-42F7-4EA0-BDBA-EA7F136D8D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da230b2453063c2e8284ccf935a3a99f21f24aa7","datavalue":{"value":{"entity-type":"item","numeric-id":4705350,"id":"Q4705350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$F8DFCC93-08F9-4C8E-9646-E4E3D19C88BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67bd9f8e5ffa9599572937bb900028da44c01b08","datavalue":{"value":{"entity-type":"item","numeric-id":1842570,"id":"Q1842570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$E95C0943-6F65-4B4C-84D9-696177467F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db3529d0e7313985d6ecaf8ffc94ad7faeb7183b","datavalue":{"value":{"entity-type":"item","numeric-id":1320672,"id":"Q1320672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$7B5F4505-D3B2-4692-A205-7D718270F0C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12ebf3acaedacad6ebbc5abc828abd1e276e4117","datavalue":{"value":{"entity-type":"item","numeric-id":3933016,"id":"Q3933016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$26157E9B-8B72-4B2F-96F6-0FE095471703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a998f318405fc477f47b3c0adacc0d1a8f1414c","datavalue":{"value":{"entity-type":"item","numeric-id":3211352,"id":"Q3211352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$BBAAFBEB-C993-4CA5-8129-FB8E599680D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2559c4bfe9a39927402ec0ef80939d1c671323e","datavalue":{"value":{"entity-type":"item","numeric-id":5176030,"id":"Q5176030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$F7428546-494D-4523-811B-8AD26D0A579E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c02823accf1c76827af894083984037631e0fd95","datavalue":{"value":{"entity-type":"item","numeric-id":1923855,"id":"Q1923855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$10FEFBA0-0C90-45DC-803E-4473A329DBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ddcbcf7a005757d3510746aeaaed61468b98523","datavalue":{"value":{"entity-type":"item","numeric-id":4032938,"id":"Q4032938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$9DB35354-6A89-463A-A465-E65B05ACB875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6127c8a3d94405dc98716287d13c18072bd1b2c7","datavalue":{"value":{"entity-type":"item","numeric-id":1593404,"id":"Q1593404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$EB069A57-6BE8-4B8C-A3B2-03CE653DB85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e77d78030bb29a731a47c15ddbaef3a7da691481","datavalue":{"value":{"entity-type":"item","numeric-id":5675788,"id":"Q5675788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$8D28B19C-D0FA-4BA2-B236-948AC3094662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccfd7e3fb1b53648f3a8a63c0204d8126f9fd8c3","datavalue":{"value":{"entity-type":"item","numeric-id":5932755,"id":"Q5932755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$921FDE6B-F003-42BD-BBB3-199813490474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bce6d5b6942e78edb940878b5186fb69d93ae534","datavalue":{"value":{"entity-type":"item","numeric-id":4286300,"id":"Q4286300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$6358AF68-8CB9-4944-AAE1-50F7C829C06F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$037B064D-414D-4D3E-9856-5D9A16099638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b89ebaf98c8fde5131cef04a549821dcb75fe243","datavalue":{"value":{"entity-type":"item","numeric-id":5511421,"id":"Q5511421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5917579$BA104346-9D31-4C5C-B69F-ED85DFDF8530","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f241b6f47ff31b3d21062e9b041b713820af7b3","datavalue":{"value":{"entity-type":"item","numeric-id":2903520,"id":"Q2903520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a4e41177fd279c9bfac784f69372371584c4461","datavalue":{"value":{"amount":"+0.8604441285133362","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":"Q5917579$3D1D276B-21E5-4FC1-AD96-C2AA76C25A97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be0e28dd27538c51efd1df2af418b9b8cac8dbda","datavalue":{"value":{"entity-type":"item","numeric-id":3192039,"id":"Q3192039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70ddf458c7ca177096bf1becff535a842ad1d7d5","datavalue":{"value":{"amount":"+0.8287360668182373","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":"Q5917579$1C1B962C-AB4B-45C9-A2C2-E9B450DB0410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"691cdeb9dd52e4ccf40fa35ac21977743264dc1e","datavalue":{"value":{"entity-type":"item","numeric-id":4705350,"id":"Q4705350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ef245ec90f35989e7cba684c4059407555b6a24","datavalue":{"value":{"amount":"+0.8285079598426819","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":"Q5917579$B0C3CD7E-431B-469B-A57F-550047A1BAF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be50e5e9c7db971c88cb8dd5666f1decf6a89aed","datavalue":{"value":{"entity-type":"item","numeric-id":3069905,"id":"Q3069905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b29c4920d9142ddd77a032e4398208e970484c9d","datavalue":{"value":{"amount":"+0.8263686299324036","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":"Q5917579$7268FC4E-C2E9-420E-98C7-0246400B120E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffa752825e7380c05abc307da269c2fcaccc7302","datavalue":{"value":{"entity-type":"item","numeric-id":1842570,"id":"Q1842570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f0ae380843573bab8263407c4307a77caa4aee6","datavalue":{"value":{"amount":"+0.8236492276191711","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":"Q5917579$ED7453DF-EB72-4FBB-BBBB-ECA419D6F506","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5917579","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5917579"}}}}}