{"entities":{"Q5958322":{"pageid":8135124,"ns":120,"title":"Item:Q5958322","lastrevid":47755078,"modified":"2026-01-02T14:52:28Z","type":"item","id":"Q5958322","labels":{"en":{"language":"en","value":"Decision tree approximations of Boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715323"}},"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":"Q5958322$46EA96D9-6D06-46DB-AD1D-744A219C9100","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd909b3438fb8a9c945d024ce05b5b46c82161d7","datavalue":{"value":{"text":"Decision tree approximations of Boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958322$6F01395E-9BE5-40E3-BB4B-C480179EB843","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c81e43604fde341841ed9ff8945bc49cc6babc8e","datavalue":{"value":"0988.68136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$B2B38B6B-DA4C-4323-AC23-5AB9926FFA83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c919fc603185d1012b2a5273fa3df62f1545efbc","datavalue":{"value":"10.1016/S0304-3975(01)00011-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$AA6BE948-698E-4D6D-A4AA-B992A3C288BC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9014bea74ad5ac28409f874f279201ed39e54a32","datavalue":{"value":{"entity-type":"item","numeric-id":691441,"id":"Q691441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$1447386A-1FDC-4F44-8CCE-AB84659412FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3699a0ae2ee87f1ab72ed90c16e98977e8bce8fd","datavalue":{"value":{"entity-type":"item","numeric-id":235686,"id":"Q235686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$718F5AED-4477-4E74-A46D-8E847C8A4697","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":"Q5958322$A91794F6-AD87-46C9-A5FD-38A8B8D2114C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958322$3CBB292E-5975-4BC3-BD26-6717F6A495B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64177dc2e2330747f6b048877dcecb1c9fbfc71f","datavalue":{"value":"Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function \\(f,\\) say as a read-once branching program, one can find a decision tree \\(T\\) which approximates \\(f\\) to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent \\(f\\) and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function \\(f\\) instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958322$544C0631-584C-498E-BBE5-4E614F3ADCCF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$28ECE2A7-6623-4CDA-9D2E-8B7952BBACF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$B429E830-B4AE-4A95-A8FB-62AA6687D9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25c8936003d39e41a9c8a541470f5aac0fe1fa32","datavalue":{"value":"20B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$C14F2114-7B99-41E2-B3A7-6D6C88DD6793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$9B4E1532-2E41-4542-A0D6-9C559FCA07D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$0BCF5361-93EE-4369-A8F1-E3DB0A84D94A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"758f2f1c8f28735838a71f1f1b7d0dde9e55a8a5","datavalue":{"value":"1715323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$C842FFB7-3C48-47B4-92B7-357AAFE748AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958322$CE9080D4-389B-4B2B-911A-2ECA2B12CB6D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"53582d8e8183f772ef86ccc14223ddf4262a9ccd","datavalue":{"value":"Q56340226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958322$F8342F11-780A-4B66-837A-11AB34357A76","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":"Q5958322$8DE4088B-6F04-4FA5-9F3A-BA2F1ABD9B08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e0bce9bac897f983fda4ecc0cf3bbfd3856074f","datavalue":{"value":{"entity-type":"item","numeric-id":1144943,"id":"Q1144943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$A15E6764-CB94-4B06-AE1B-97E67B2FACCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1f4496e9c5097df00995c9eacd5b0b3cb6d9ba4","datavalue":{"value":{"entity-type":"item","numeric-id":1108056,"id":"Q1108056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$2DBEF743-6B6E-4EC2-A793-B94CD6DBB052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f275b0c7960baec2620149acfd97bb31ebbe0b06","datavalue":{"value":{"entity-type":"item","numeric-id":2506483,"id":"Q2506483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$D05DCAE8-48FF-4E2D-A0FD-169512049BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76a622793d73d01dcfafffdc8effeec9101cb571","datavalue":{"value":{"entity-type":"item","numeric-id":4252715,"id":"Q4252715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$03188469-447B-426C-B354-F0E9B34CE09F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"246209d8ad699ed7e7ce5e111f628718396bfb05","datavalue":{"value":{"entity-type":"item","numeric-id":1127393,"id":"Q1127393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$36502ED7-8A56-4EDD-8CCE-048F8DDE63A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e622144574aa2c2ba883d6895d25b36bd5a3b46","datavalue":{"value":{"entity-type":"item","numeric-id":1823009,"id":"Q1823009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$F85AD829-AC31-40E8-90F0-D1B3AB28E96C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$5DF80DCC-2DC0-4C47-8F12-D20C40A9DE4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7ac4418cdddb28b6e8704f0c8cfb524c4915f16","datavalue":{"value":{"entity-type":"item","numeric-id":1606947,"id":"Q1606947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$2539CCC8-36E0-4B26-87BB-5C7667694A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00997f32c2231ba5e073181adf6fee4f2890107c","datavalue":{"value":{"entity-type":"item","numeric-id":1228355,"id":"Q1228355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$B3112237-7FA8-4C30-8D13-610E3AEA9CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e274441c8c0505119f5dca2d2fe135998d1faa1","datavalue":{"value":{"entity-type":"item","numeric-id":4306374,"id":"Q4306374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$455DF6BA-1BCC-46FC-A1BA-9F3EF5852F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27fdcb8cd08178090693747ae37e0df81770b93c","datavalue":{"value":{"entity-type":"item","numeric-id":5249043,"id":"Q5249043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958322$8CDC9A70-AB69-4530-90F6-C214E0061EC8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f3716bf1f552521ca94931cdf5e3ea95f0d3582","datavalue":{"value":{"entity-type":"item","numeric-id":1823009,"id":"Q1823009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6f293f37ca8d697d909a0a95650561406d449fe","datavalue":{"value":{"amount":"+0.8084820508956909","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":"Q5958322$C7FB25E4-F5E4-4B21-B682-8DB45642E69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24e30f59bde28743f35c79117aef34d49a9759a6","datavalue":{"value":{"entity-type":"item","numeric-id":4277547,"id":"Q4277547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"679522c18161184cdcdba98fa3c709bef2cf273a","datavalue":{"value":{"amount":"+0.7983200550079346","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":"Q5958322$7C652AA1-2617-4191-94B4-28E347289E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6079a2050460e405e13b4de91dbe6b05bf1ce62d","datavalue":{"value":{"entity-type":"item","numeric-id":3507522,"id":"Q3507522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f93fc322476b09df9c5948535579fc3d29b98f72","datavalue":{"value":{"amount":"+0.7956785559654236","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":"Q5958322$54C32518-CDB9-4BBE-A290-BA14F4D7AFEA","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":"b56360a5553d2fe9a3c45ad2b245de30cbdf721d","datavalue":{"value":{"amount":"+0.7948321104049683","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":"Q5958322$24F18E7D-C6DC-4457-9DE8-7C44CDE3C56A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc82ef8151cfc54e3b62341677ff88b86159751f","datavalue":{"value":{"entity-type":"item","numeric-id":2506483,"id":"Q2506483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b82e6f81157929149f473eadf5706864ea26bec","datavalue":{"value":{"amount":"+0.7858719825744629","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":"Q5958322$A779A288-057E-4D9B-BBEC-4AB42C4B22F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958322","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958322"}}}}}