{"entities":{"Q2479315":{"pageid":2490058,"ns":120,"title":"Item:Q2479315","lastrevid":74219763,"modified":"2026-04-14T19:01:53Z","type":"item","id":"Q2479315","labels":{"en":{"language":"en","value":"Finding a vector orthogonal to roughly half a collection of vectors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5254041"}},"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":"Q2479315$6DC708DD-8634-469F-9557-519BBB5BF67A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82c3c7943feb5216aa8317afa3550abf6d4a6285","datavalue":{"value":{"text":"Finding a vector orthogonal to roughly half a collection of vectors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2479315$B77B8167-9436-430A-8F01-ABD21E363DEB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea53caeef09dd31938c4572f04cec5fd0e998069","datavalue":{"value":"1140.65033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$F0CDAD6E-C30F-43B4-AC97-CD45FABDCD8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"464f0fdc8f0ac24a2780ce4feed43050ac87ac2f","datavalue":{"value":{"entity-type":"item","numeric-id":384927,"id":"Q384927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$7AA406F9-C71E-4634-AFC8-8BB3199F3EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5c6184dbf168c93692fa6f8742ab0b2d67a8b9b","datavalue":{"value":{"entity-type":"item","numeric-id":287066,"id":"Q287066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$44EC9761-FCD2-40E2-8CD4-CC8615C51684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f1d44d27959f859898fa170c96149cb9cd1f4dac","datavalue":{"value":{"entity-type":"item","numeric-id":451112,"id":"Q451112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$04CF74AA-E13C-4889-9103-375DEF67F867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb00eee60b30ec4f0a161ec2662298db8751de2","datavalue":{"value":{"entity-type":"item","numeric-id":458599,"id":"Q458599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$0F4283D4-013F-4C78-8A78-37F7488C9EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"422d41f94f8a39580a8eaa67cd40c776a7c16584","datavalue":{"value":{"entity-type":"item","numeric-id":858107,"id":"Q858107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$36DDF8E2-CCEC-449F-9781-0A0B4AEDBB83","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$AD9B3952-3EED-46B0-B51A-B5106EF2C9C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5e0cdb440ca46d9b8c69635fc01191f2bcf2170","datavalue":{"value":{"time":"+2008-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2479315$0DE713D9-E573-428D-A4AD-6F587F3BA60A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"725584888e57f6e5afb4509351ddd5b7710352ce","datavalue":{"value":"https://hal-lirmm.ccsd.cnrs.fr/lirmm-00292703/file/jc.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2479315$A367C028-7749-45F9-8FD1-D1D00EFA952A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c2b87132012fabe37937056559f8acfc63d1aa4","datavalue":{"value":"It was shown by \\textit{D. Grigoriev} [J. Complexity 16, No. 1, 50--53 (2000; Zbl 0951.68024)] that for any family of \\(N\\) vectors in the \\(d-\\)dimensional linear space \\(E=(F_2)^d\\), there exists a vector in \\(E\\) which is orthogonal to at least \\(N/3\\) and at most \\(2N/3\\) vectors of the family. The authors show that the range \\([N/3,2N/3] \\) can be replaced by the much smaller range \\([ N/2-\\sqrt{N} /2,N/2+\\sqrt{N}/2] \\) and give an efficient deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479315$6FC93170-5F7A-4002-8125-702B3659D4ED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f9e4f5ee2ff4efa1345e650ad5729a2a6fa6cff","datavalue":{"value":{"entity-type":"item","numeric-id":589121,"id":"Q589121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$96C88A9F-80A8-45AF-9B84-D03E1F603C66","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$3E1D7C41-234A-4950-8DFE-EFE198DDA3B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$999733D8-C033-47F7-9B16-C31F6CE1A82D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3be4ad80ce8780e61f2afdf5234325511e85650a","datavalue":{"value":"65F25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$A552A565-96E4-4DE6-A48F-BF538D21DCF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$A7148C6C-10CD-4AD5-8BE3-F1B2B8B2DB4E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ca4b9f225f3aca1aeef301f8bce36197151e2a6","datavalue":{"value":"5254041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$7C46745E-FB6D-4914-AAA9-FABEF083FAF3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479315$17894874-4E12-46E1-A861-37CF2F0E95BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50e4e06d9e28eb2b5161a8b77486cae9897ae53d","datavalue":{"value":"decision trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479315$7308D648-DB3B-47F2-AB79-28E4E64D7D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479315$0DF54E67-8DC3-44DE-9A33-6E9F5A20CD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479315$96924C7C-F435-4D0D-BFE4-A85A1E458EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"855903369365df89e1d14db94a90c5517cb247d7","datavalue":{"value":"orthogonalization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479315$02C0B112-C1FB-4FB5-B3AC-CA117F265B10","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":"Q2479315$DE7101B5-E9F8-4F34-AC56-8C8F5E729F15","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4d9979376cbeaf337e3e41d532f721b94b820450","datavalue":{"value":"W2161469686","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$AC2D6CEF-C309-4D5A-91DD-B9A83E42E93F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9208528a9398d42022a83d3910fdcc8477ab6c6","datavalue":{"value":{"entity-type":"item","numeric-id":2784326,"id":"Q2784326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$E903FE8A-950E-46E4-84B2-A19D97E66C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5699694bdd1074c4792cee7c3f50ae33d8eb62c2","datavalue":{"value":{"entity-type":"item","numeric-id":4718423,"id":"Q4718423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$402D3755-CD97-4DF4-93A6-6624918AE31C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31b9fbcf5b103d19429f8ba43bde08b37cbb29d","datavalue":{"value":{"entity-type":"item","numeric-id":3470109,"id":"Q3470109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$599ABFBB-5DE4-4AAC-9C95-B653560EE5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ac5048d78dad669dbfd0ea8784dcc1edbb6746f","datavalue":{"value":{"entity-type":"item","numeric-id":4542570,"id":"Q4542570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$73963AE5-656D-45FE-97BF-55E40DF9E251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c928238a0b9a59eb2f4fd1a88eb9d1121ae53e37","datavalue":{"value":{"entity-type":"item","numeric-id":2754200,"id":"Q2754200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$22A7EE8D-9CC6-4AEC-9D46-09D0F8C67CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4387c64dd036e7aa64a14eb969043be221cc39b","datavalue":{"value":{"entity-type":"item","numeric-id":1977139,"id":"Q1977139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$CB17C179-90C9-4AF1-B1B6-C612740C106B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c773a96a1b979023d4aaabc35aeee7103f31046","datavalue":{"value":{"entity-type":"item","numeric-id":4501520,"id":"Q4501520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$8FC0C595-2FC6-4E93-8105-A34A371A2E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc05802655dcb9450750f37a8aa17460c48bc4b","datavalue":{"value":{"entity-type":"item","numeric-id":690248,"id":"Q690248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$BBFA02C5-DAB0-4448-B830-F3311F8DB3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74562e1bfcbeccc3b58591b3fa2554f211008cea","datavalue":{"value":{"entity-type":"item","numeric-id":3768396,"id":"Q3768396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$4EC9BAC0-7009-43E8-AF61-9EA501BE9863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03789c1b867b6455d209db88a5ef320f8e404383","datavalue":{"value":{"entity-type":"item","numeric-id":1342858,"id":"Q1342858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$35C438EF-698C-4F65-8DB6-EECAC7C67C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1959864393df920e2e4af3b07395c2ebb46cc880","datavalue":{"value":{"entity-type":"item","numeric-id":1099953,"id":"Q1099953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$341DC4AE-171F-4C1B-83AA-4B1708E957F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4350f19c99bfa1cb7ae940852320e2e0306d00b1","datavalue":{"value":{"entity-type":"item","numeric-id":287088,"id":"Q287088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$86F71A40-AEBF-42C3-AB48-3411A04E6402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"624abf0da839d476906101af8b6d74820b65cb0e","datavalue":{"value":{"entity-type":"item","numeric-id":4393484,"id":"Q4393484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479315$A11B552C-B2C0-4114-8445-D9DF3C716FAB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3fed9bb78797323be948cbd332964d81450b90ab","datavalue":{"value":"10.1016/J.JCO.2006.09.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479315$29B5FFF1-1848-41E6-B397-2936E8DD54F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9389274b79e2ab6526953f043cc0e8145c64038b","datavalue":{"value":{"entity-type":"item","numeric-id":1288511,"id":"Q1288511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c533040065ab61ace4742053b704281b450dfcc","datavalue":{"value":{"amount":"+0.7754055261611938","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":"Q2479315$728B8BFF-680C-482D-A2F4-05138AB0CC7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0afa61e917d4dc9bb0c3284f75ff2fe9820ad22","datavalue":{"value":{"entity-type":"item","numeric-id":1205349,"id":"Q1205349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c533040065ab61ace4742053b704281b450dfcc","datavalue":{"value":{"amount":"+0.7754055261611938","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":"Q2479315$75C3EFA5-2484-4DE8-BB1A-C2C4E751FCB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ccb0c87ce47cf70b3d3e233d8b1c870bc5a78e2","datavalue":{"value":{"entity-type":"item","numeric-id":5384097,"id":"Q5384097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0b3e399931c975bcdb31f6fff9f047c1d50364b","datavalue":{"value":{"amount":"+0.7405765652656555","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":"Q2479315$8B3FFAE0-66ED-4F43-A57B-2CD61C87D852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"485edbc4c0533f9a6160dc89131f7155d05e20ca","datavalue":{"value":{"entity-type":"item","numeric-id":1744760,"id":"Q1744760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c1d1441e72e83af9f062ee26ae6b161183f545c","datavalue":{"value":{"amount":"+0.7399741411209106","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":"Q2479315$D183CD2B-5C0D-492A-9393-F3F49C986616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef9737bd9ed384afcb93906a0062cfe184d59a48","datavalue":{"value":{"entity-type":"item","numeric-id":456304,"id":"Q456304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81b4782884d56af67707dbeb86efd6014c3eecd3","datavalue":{"value":{"amount":"+0.7350566983222961","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":"Q2479315$2A116934-8E3B-4FDE-B47B-3E0B75703CB7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding a vector orthogonal to roughly half a collection of vectors","badges":[]}}}}}