{"entities":{"Q2746911":{"pageid":2757650,"ns":120,"title":"Item:Q2746911","lastrevid":83074049,"modified":"2026-05-07T05:55:19Z","type":"item","id":"Q2746911","labels":{"en":{"language":"en","value":"On randomized complexity of functions approximating the majority function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1656843"}},"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":"Q2746911$B42172E2-4C93-4866-9391-70E7469E8680","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"691f97603345b74fd3988a4e99eaec2c00edd66f","datavalue":{"value":"0973.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2746911$CA855D4F-D67F-49C9-8C96-162E07756B04","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1542a73ffc22f2d225abd6fdd963c595b4d028f1","datavalue":{"value":{"entity-type":"item","numeric-id":187705,"id":"Q187705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2746911$4DB3E931-646B-4456-8EE6-6619B9479CAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3affb76f39280a6ff66de0de3b3828b69fcb28c0","datavalue":{"value":{"time":"+2001-10-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2746911$49DD17BA-1D33-429B-A313-7678D5A91F1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2746911$2C1735D6-D386-46F9-B967-E67BA1A6E018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2746911$CFC50053-6812-4F53-B273-6F85FC6A3902","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44a132b666605adf0cebdb186eba1db17813cd90","datavalue":{"value":"1656843","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2746911$A6364FB7-A58B-4E3F-9633-26925F23BD21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2746911$E1EEB320-2210-4DDC-AADE-0311B7E69090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2746911$F020CF50-F18C-4243-AFAA-FCFE2D523A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2746911$E9BF7C1F-ACF7-48F3-A0F2-55CC944C3422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f7dbe30be9510d1b6326726073959a3e04a0cda","datavalue":{"value":"RAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q2746911$130669F4-EF01-4231-B20C-D27E0441BA0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d5818180a752276cbb3e53d99b94300b47e1df4","datavalue":{"value":"random number generator","type":"string"},"datatype":"string"},"type":"statement","id":"Q2746911$1926CDB8-574C-4B7A-8A76-C45877355264","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":"Q2746911$D1747996-9EA5-40B3-9E77-191AB996F8DD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"228f8649f96538194ded7862fe02a5b3d1c78200","datavalue":{"value":{"text":"On randomized complexity of functions approximating the majority function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2746911$81619DF7-632C-4E1B-AA2A-FCAC8F8A275D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"75dbe44001945ccc889d4ace23e71d51974d13f4","datavalue":{"value":{"entity-type":"item","numeric-id":6768473,"id":"Q6768473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2746911$5B0806A5-EE5D-4A22-84AD-B167D9BA15E5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c4b6b4baef59866d759a135eb859cb405a1775c","datavalue":{"value":"The computational complexity of partial Boolean functions approximating the majority function by a modified RAM with a random number generator is considered. It is shown that there exist partial functions that approximate the majority function. The deterministic complexity of these functions exceeds their randomized complexity by the factor \\(n\\) (up to the order), where \\(n\\) is the number of variables of the Boolean functions under consideration.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2746911$C1092905-CB1F-4A57-9A00-E23AE3D9AE88","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3633e99a049bd141b95f5a1ad01a2839677008c5","datavalue":{"value":{"entity-type":"item","numeric-id":5901987,"id":"Q5901987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6a5094dcfdbab8b88970d3fd45007d4724aa2c0","datavalue":{"value":{"amount":"+0.7857726812362671","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":"Q2746911$91239B79-FC40-48A9-8268-9BEB30983F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed199d95c50b1d9eba3583b6b489c4305e4630f9","datavalue":{"value":{"entity-type":"item","numeric-id":1209362,"id":"Q1209362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"070ba5d7e2f477686e04b71e46cbe7a357705944","datavalue":{"value":{"amount":"+0.7747036218643188","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":"Q2746911$5D7B025D-C557-4FD4-BDC0-CD4E8AA45237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"783a8c75545fffef7efb6d68022ae522ac8be81f","datavalue":{"value":{"entity-type":"item","numeric-id":3691581,"id":"Q3691581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2423cd5e29d29213379667e4329fa3219784ba14","datavalue":{"value":{"amount":"+0.758537232875824","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":"Q2746911$3AD3A08A-4533-44C9-B197-4B430AB2941B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9a5d390e970f871bfcec3de13ca6f1e9d17989f","datavalue":{"value":{"entity-type":"item","numeric-id":3974564,"id":"Q3974564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97c27ef0ec477eb008f7f79e3d965e2114c1c7c2","datavalue":{"value":{"amount":"+0.754953920841217","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":"Q2746911$EB4A8BB4-803C-4266-AA31-4AC9B4779019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"576c9bcf0bc096ca62242282d9f640cdbecbb4bb","datavalue":{"value":{"entity-type":"item","numeric-id":3012816,"id":"Q3012816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8012ad57b023077c40541cc0162f45a1b3df279c","datavalue":{"value":{"amount":"+0.7531828284263611","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":"Q2746911$1E3BD6F6-B80C-489F-A71B-8854109212D7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On randomized complexity of functions approximating the majority function","badges":[]}}}}}