{"entities":{"Q5932642":{"pageid":8109444,"ns":120,"title":"Item:Q5932642","lastrevid":47619070,"modified":"2026-01-02T05:53:47Z","type":"item","id":"Q5932642","labels":{"en":{"language":"en","value":"Testing monotonicity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1603948"}},"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":"Q5932642$17071D85-4650-4401-B637-A21CB99463E7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b4b2e6becc033b28699765eeda72c18096e56db","datavalue":{"value":{"text":"Testing monotonicity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5932642$0F597F2A-4AAC-41AC-911D-A0C966093798","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6908e720ec336dd81bb591b8a733a6e5a5b56b21","datavalue":{"value":"0964.68148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$168E1628-1638-4601-9D4A-351298EDF92C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cecf1ef8f97c75d3f636331253c64cfc37610336","datavalue":{"value":{"entity-type":"item","numeric-id":178474,"id":"Q178474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$3058A1F0-42EE-4A23-AD13-0FFBBCAB5D04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca5b86eb868915c377d9f8399026f0f4a4bfbb0f","datavalue":{"value":{"entity-type":"item","numeric-id":178476,"id":"Q178476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$F4DDAE29-55BD-40D0-83F3-F2220EAD534C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e10480e046eb228ee7883bfe3d51ac4b35b07ad9","datavalue":{"value":{"entity-type":"item","numeric-id":171921,"id":"Q171921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$25909D88-F843-45CD-AD13-A76968A74EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96e37954b3c16ec47a5d1dbdc807326b30e72c45","datavalue":{"value":{"entity-type":"item","numeric-id":178477,"id":"Q178477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$C9524FEF-F624-49D4-9CDF-2C36114132A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"46a19aabcc7af8f26d97e8183ee72dbc292f645f","datavalue":{"value":{"entity-type":"item","numeric-id":6480587,"id":"Q6480587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$226685AE-4AEF-4B5E-92B1-BFF9B92D4E66","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$191DD217-782C-4AD1-8A68-5071A1D8EFA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d0cc84dbcc23d45b1f8ffdd4c75be7f49927c856","datavalue":{"value":{"time":"+2001-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5932642$7279AEE8-BBDF-48D8-84BE-79CAB1D459AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ff38958987bb3019844fb1f09f184a6bba69294","datavalue":{"value":"This paper provides a valuable nontrivial contribution to the area of learning and to the study of the power of randomisation. The following task is considered. Given a Boolean function \\(f\\), one has to decide whether \\(f\\) is monotone or far from being monotone (it differs by more than on a \\(c\\) fraction of inputs from any monotone function). The algorithm may ask for the values of the function on arguments of its choice and its complexity is measured in the number of queries. The author designed a randomized algorithm that   (i) accepts every monotone function with certaincy,    (ii) rejects every function with distance c from any monotone function with probability at least \\(2/3\\), and    (iii) uses a number of queries that is linear in \\(1/c\\) and in the number of variables.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5932642$CC1B32B3-93F6-44D6-933F-BD141F526F77","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5932642$64257BA1-98CA-4EA9-B96A-E8214FC3C129","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$F068992A-AC4A-4B58-80D1-D0C34ECF5E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$E3BC16A3-F54D-4059-BBB0-84714FE84675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$7757023E-9DD8-4F7B-B6E4-11307743569B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bde138a3df28e6250f416281914a936f983d048d","datavalue":{"value":"1603948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$F7CB2267-B16C-4B09-BF68-8B571E662C9E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"137da6096ab360af96c26c797f3b47624d3f3958","datavalue":{"value":"learning randomized algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5932642$57B9ED12-BB9A-46DB-9337-E260970CF4FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b93ba200c5c60361d4cf328ea593f23be1c36a85","datavalue":{"value":"monotone Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5932642$8CE807B1-F45F-4E92-A516-82524D7A17A3","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":"Q5932642$4E25F86D-9647-4BD5-9471-5012C244C839","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2983d87a5d49f6530b3fd6ba431c79f36148e271","datavalue":{"value":"https://doi.org/10.1007/s004930070011","type":"string"},"datatype":"url"},"type":"statement","id":"Q5932642$D395BCF8-617E-43FA-91D5-1200D1177CA7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a628750267c6fffbdb1620aa6f9b6ebbe92d4a4","datavalue":{"value":"W4235805661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$FAE76D44-A099-4EE5-A8C0-CD68BA1DBF3D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b631a37f9cb9ad3833852431f3c32e9ee8a24381","datavalue":{"value":"10.1007/S004930070011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5932642$D7632650-3496-4D05-BF34-7D6C53CA5AE3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"990e90d963007c81c0c720975732d1e67abb0a32","datavalue":{"value":{"entity-type":"item","numeric-id":2941544,"id":"Q2941544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6b6f1051966faa296cea38736853a7b0b627b73","datavalue":{"value":{"amount":"+0.8484657406806946","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":"Q5932642$D40E3DA1-B1BA-49CC-8033-3379CEF52245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26c34fb65e9aa101c8178d4d41b73c4c24825c2c","datavalue":{"value":{"entity-type":"item","numeric-id":4941829,"id":"Q4941829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f16937abd5bcab726cdd882a3445cb82c3da1baf","datavalue":{"value":{"amount":"+0.8448477983474731","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":"Q5932642$5BB526ED-D0F8-4737-9081-206EEF1CF341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb886d3c43c5dede9eb3584a330ed90c36fad542","datavalue":{"value":{"entity-type":"item","numeric-id":5313026,"id":"Q5313026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"793162c82fcf7a4427e05f80c17125e6fced46b0","datavalue":{"value":{"amount":"+0.8448472023010254","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":"Q5932642$33211B6A-6410-4B8C-90A2-88DAA106C80E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5ce4d1e15eb196ed157e63562e190247bb1fe1d","datavalue":{"value":{"entity-type":"item","numeric-id":4562273,"id":"Q4562273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aebb515a63e9ece49dfadf25f48b3376fd1b9d7","datavalue":{"value":{"amount":"+0.8414490818977356","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":"Q5932642$1445DEC1-645F-4CDB-A4D9-A32324FD8F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7674b56582faa9365099eb75077bab1398cadf84","datavalue":{"value":{"entity-type":"item","numeric-id":2805510,"id":"Q2805510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32e0653a6532dca2f7d413c611f74fae7898c22c","datavalue":{"value":{"amount":"+0.839157223701477","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":"Q5932642$D7A37849-B84D-46EB-AFC5-2B500E1E0964","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5932642","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5932642"}}}}}