{"entities":{"Q1067786":{"pageid":1078538,"ns":120,"title":"Item:Q1067786","lastrevid":69771528,"modified":"2026-04-13T09:16:50Z","type":"item","id":"Q1067786","labels":{"en":{"language":"en","value":"Lower bounds on probabilistic linear decision trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3930350"}},"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":"Q1067786$F66F354E-8C98-4931-9981-4733B7C93CD2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"74ac75aea93f4d724ba44e814b7e8261b255ed37","datavalue":{"value":{"text":"Lower bounds on probabilistic linear decision trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1067786$7E04B677-D780-4551-861C-21510482A6B0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c5fbe4c4092a915e31fbdf031a751582af8733d","datavalue":{"value":"0581.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$F427654F-0EE3-4201-8BFC-1142693C8299","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0bf9288d3433fc3d8736805637c5582b3babafc0","datavalue":{"value":"10.1016/0304-3975(85)90210-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$28AE6AE5-1812-49F9-8D60-3A23E3A7833C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74fd6b3a8df291eb0ef14a7442cbd4d786a23aca","datavalue":{"value":{"entity-type":"item","numeric-id":804294,"id":"Q804294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$E6FC75E1-C5D3-48FC-A621-BB01E3C6ECA3","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":"Q1067786$7D4C3806-96A5-4E8C-9924-CFB209303CFF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1067786$18A9B101-146D-41CA-92DB-453187B82A5F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef7ea6c65b2d0b60c0f1fd93e5f195dde8964faf","datavalue":{"value":"Probabilistic linear one sided decision trees are examined. A technique is developed to derive lower bounds for the average number of comparisons in such trees from lower bounds on deterministic trees. Using it, \\(\\Omega\\) (n lg n) lower bounds are derived for problems such as element uniqueness, set equality, etc. Standard lower bound arguments for deterministic decision trees are shown to be valid for probabilistic decision trees. Nevertheless, a simple problem is described where use of random choices provably saves time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067786$D6EB75FD-9B0C-4160-88E5-C3A8C103B769","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$157BC7EE-454A-45EF-979A-AB9DE56BAA55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$C075B92A-8BDD-4335-AC1D-5B6900AC6E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$451293BC-C39E-46ED-B624-426A5E4A5EB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e44b60df19ceb853c621639c917e748ef1165129","datavalue":{"value":"3930350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$8FE2E7A8-FED2-4B80-86A7-4E45501577C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e569e07a49c82ee4107766a600078715f7a3daaf","datavalue":{"value":"probabilistic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067786$DAA4C056-4CD3-48A9-9BCA-D3903CEC99ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3e3e8147c5b5a1f1f65b21f0ed2b08658ee2d19","datavalue":{"value":"element uniqueness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067786$572C9F31-B434-44C8-B861-5274236036AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f17695ec6e2386ef60513744d597956b154a4826","datavalue":{"value":"set equality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067786$B5AB6C5D-A35D-46EE-B613-D1B6AA940756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8de22a9f14a1f5fa52e9d747fa14ff84d1deb6b","datavalue":{"value":"probabilistic decision trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067786$11DC36B3-9730-4006-9830-AA837CCC7296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1c46559e36a9584cecec90e62da154b03c0f14d","datavalue":{"value":"random choices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067786$39A09D01-D7DC-4DFD-B3A0-470CCE6DA64E","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":"Q1067786$F55291A0-3BDE-4449-8E80-BA79D8225B51","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8276b0453d20b47dca3142d1f1fdef2706827bb","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90210-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1067786$31D4E994-DE0C-4848-B93A-E4BE6F61FC34","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d37b87a8736c21b3e92952d97ddd1ef50f0e774a","datavalue":{"value":"W2026325622","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067786$2F33A807-4906-4F96-A985-44EAC11A3468","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95be383f4814efc07c25732619c12742108f623","datavalue":{"value":{"entity-type":"item","numeric-id":1259164,"id":"Q1259164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$E8250021-6D97-405F-9B79-22389E231715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfdc76fb3562ef6f4c9173dc95ee70d4835105e7","datavalue":{"value":{"entity-type":"item","numeric-id":4157950,"id":"Q4157950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$AEC4CD99-F2A6-4B8E-95F5-D5663F01FD13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cf1cbc903427b9dfc0dbb5cfe0f58382818bfac","datavalue":{"value":{"entity-type":"item","numeric-id":4077449,"id":"Q4077449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$BF7C9DCB-1BE0-4368-A5D3-A00184ECDF95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43d43f926304af656560186bb34ae2943c1894d1","datavalue":{"value":{"entity-type":"item","numeric-id":5659062,"id":"Q5659062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$99902601-7920-4D41-B2C8-EE6A2C867054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"260e7e66fdf79381c9a7667ebc2df65dbfcd85a4","datavalue":{"value":{"entity-type":"item","numeric-id":3926036,"id":"Q3926036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$742E48B9-6262-4E67-B821-39C63D5BFDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf851580ae91acae3bb4962517461ba598b1a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":3893331,"id":"Q3893331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067786$0388B771-CF3A-4DDB-AD7D-65155F1567B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ca70900fe28fd9c56ca8d8e67c4465486375b1d","datavalue":{"value":{"entity-type":"item","numeric-id":5175129,"id":"Q5175129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eba182af08a0b7d322d864a8d813aad2318ae5e1","datavalue":{"value":{"amount":"+0.9497911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$DD6B9AB3-47B7-4362-B21D-D56D933B4A54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6f2585fa54604a2bf576ee757574f65ff7b4136","datavalue":{"value":{"entity-type":"item","numeric-id":3088072,"id":"Q3088072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cc5791189b98cea9819d4274ad6eb18647547a7","datavalue":{"value":{"amount":"+0.9292208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$0FCF7060-6FF3-4CDF-9326-1F1527E66012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd76e43185efebf5ae1bdf77f9c8f77fde3c9a90","datavalue":{"value":{"entity-type":"item","numeric-id":3328253,"id":"Q3328253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3208cbca41cf926e32be8df10533c6fa5de70518","datavalue":{"value":{"amount":"+0.92085093","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$AF613B77-44DB-4B27-A957-F120746E5004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"431fbf80e03e51e317094594bff6fb1733452a74","datavalue":{"value":{"entity-type":"item","numeric-id":4596650,"id":"Q4596650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed42ce17ef5d61b65b8f3d11f90afa9b451f3fc9","datavalue":{"value":{"amount":"+0.9182582","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$75330EB1-A71F-4951-B93B-62A716A6D653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"235c8c667c1fe224930938d073b6ad64d87c8565","datavalue":{"value":{"entity-type":"item","numeric-id":1917100,"id":"Q1917100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed42ce17ef5d61b65b8f3d11f90afa9b451f3fc9","datavalue":{"value":{"amount":"+0.9182582","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$945DCCC3-44FE-4C4C-9464-2B2EF4024E79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b0a3ae928bf1865b1bea59d2788cca2500c431","datavalue":{"value":{"entity-type":"item","numeric-id":4399253,"id":"Q4399253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6404db88736ebe2f6744e205329d1647e3f34e42","datavalue":{"value":{"amount":"+0.9137809","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$F896A5B1-9BD5-4099-BBC9-6F903D4392F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12d37f4d41a9254de3d653a9c8ca3493f86ce8f7","datavalue":{"value":{"entity-type":"item","numeric-id":1386178,"id":"Q1386178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1c84dedf2014bd48425b397353b1a2a4b43fcff","datavalue":{"value":{"amount":"+0.9079436","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$E9C949C2-9934-41D0-A485-3933A8C5BA93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15440e4ea5a379d41e4e395d66b14d08ae9d775b","datavalue":{"value":{"entity-type":"item","numeric-id":4228517,"id":"Q4228517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1c84dedf2014bd48425b397353b1a2a4b43fcff","datavalue":{"value":{"amount":"+0.9079436","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$E9EE10AC-E853-48F1-BE4B-1DA757E8D47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78fe4978dd1ac2bc30aeca4a87bb60246cdb9e3b","datavalue":{"value":{"entity-type":"item","numeric-id":2921737,"id":"Q2921737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a901ddd222107dc3e2b71f547bc2568a4b61201","datavalue":{"value":{"amount":"+0.89598894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$44C4DFC0-D88B-4DEC-9250-2DF7EDBBA472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b8fe4209a25fa71f6f1824e47db9ba837cda8c7","datavalue":{"value":{"entity-type":"item","numeric-id":4892375,"id":"Q4892375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abc48c0ac3bd3a823235beeb36fe87050ed029f0","datavalue":{"value":{"amount":"+0.8903039","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1067786$0E7ED443-19DB-4931-B3D2-DAC35FDB9C02","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds on probabilistic linear decision trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_on_probabilistic_linear_decision_trees"}}}}}