{"entities":{"Q628302":{"pageid":630150,"ns":120,"title":"Item:Q628302","lastrevid":51205421,"modified":"2026-01-17T05:54:41Z","type":"item","id":"Q628302","labels":{"en":{"language":"en","value":"Learning random monotone DNF"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5864302"}},"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":"Q628302$F7D7184C-B67A-4649-BDA4-43C7EC605436","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca27239d96c265b19a762395e7a876b2f8c7732f","datavalue":{"value":{"text":"Learning random monotone DNF","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q628302$AE46AF5E-DF1F-42F1-B0F6-6FEF11DCF91E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bf09cacd41554d8784b6627f9708df3ccf4f8169","datavalue":{"value":"1246.68133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q628302$3637A491-F458-4312-9612-C338AEEB0873","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4bfe8a5d03678524ccffbff39777c12a0087cda4","datavalue":{"value":{"entity-type":"item","numeric-id":628299,"id":"Q628299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$1DE3A171-0288-48F3-B14D-6D18EB7614B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ae186bfd385c7d7619e62d584c207c368d23818","datavalue":{"value":{"entity-type":"item","numeric-id":628300,"id":"Q628300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$F53E616E-C03A-4D2D-B181-A977B7A6BBFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2be8fb6e35685e07f3610c2a477e3fd665571740","datavalue":{"value":{"entity-type":"item","numeric-id":371199,"id":"Q371199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$F6EA22ED-9E79-44B6-BEE7-BFBD8BF2066F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d097f2f4bddec556ce01a97bfb7f5c85ccbad9a7","datavalue":{"value":{"entity-type":"item","numeric-id":628301,"id":"Q628301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$41C755C4-423B-46DA-A3C2-C34F57253600","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$363A903D-501C-43BE-AA24-4C5ACB84108D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea47cd398be2e1bd31e6b45d02de9148c81f65a6","datavalue":{"value":{"time":"+2011-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q628302$4EBEFD76-D935-468A-8FD0-57D541AB9EDF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d6d962fa6e3b8cbffc4edbbf56b518d0ca36a911","datavalue":{"value":"Learning polynomial-time disjunctive normal formulas from random samples is an open problem in learning theory, even with the uniform distribution. A special case is to learn monotone disjunctive normal formulas under the uniform distribution, which is the topic considered in this paper. By studying Fourier properties of monotone functions, the authors give a polynomial-time algorithm to solve an average-case version of this problem for learning monotone disjunctive normal formulas.","type":"string"},"datatype":"string"},"type":"statement","id":"Q628302$64527E2F-98C9-42CE-B0DA-3B2A4178C6B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d752cb0ef563962b57095a8fe1381c36568051cd","datavalue":{"value":{"entity-type":"item","numeric-id":189517,"id":"Q189517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$B7311A4C-5469-4D0F-A691-D8B3369B47EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c189c45b466f89dd188bd061df8c45f23f05da60","datavalue":{"value":"68Q32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q628302$57515EBF-5F35-424F-9984-AB6B9CF998F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q628302$25064243-2A17-41CB-BF00-3708ED726F9A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"437d82879bef4d48a618c1eb0a08f409d0f04168","datavalue":{"value":"5864302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q628302$B0F2A8DC-E17F-4150-936F-943E38B1DD4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d13c32acaec0f55aa8967614669667bc52cd8f80","datavalue":{"value":"Fourier analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q628302$40EF5048-9D2D-4A7E-929E-30077FAF6EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44c981e906dd6aca27c197b7f1a7dd615078a545","datavalue":{"value":"monotone Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q628302$03BB333F-9E0D-4826-A5D4-5C1FEAD87C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81a56cecd4c580bb9e8a640d3f487f2f064f44f0","datavalue":{"value":"computational learning theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q628302$44B29C79-27FF-44FD-B56D-F457FB77577A","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":"Q628302$EF74E29B-06E1-4416-8728-90FF86D30755","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"047e25c21902023cd7b2136b013260aa4a3975b5","datavalue":{"value":"https://doi.org/10.1016/j.dam.2010.08.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q628302$B69FF281-B625-41C5-ADB6-0F99C7A45D85","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"959afe5bd12888ae7b4a092618f754e554b6e6bb","datavalue":{"value":"W3021060265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q628302$7AB30C56-BFCB-42D2-A775-FE7377ED8FA5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1546b73f479557e7920218735f277b28599d8c2d","datavalue":{"value":{"entity-type":"item","numeric-id":1900981,"id":"Q1900981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$AC7F9028-B760-428C-9D4F-47985148EFB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f7829dcb164da5a51a28713181154771677e7f8","datavalue":{"value":{"entity-type":"item","numeric-id":2462500,"id":"Q2462500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$A601EEBA-4410-4493-9958-D579873B5985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7770e8c7fa22d3d851efd951bfddc490696640d8","datavalue":{"value":{"entity-type":"item","numeric-id":4420740,"id":"Q4420740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$75C7E14C-A71F-4963-9228-1145AA775D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4c2667571e92df3d173377f7d61cf49fb5bcdee","datavalue":{"value":{"entity-type":"item","numeric-id":2817616,"id":"Q2817616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$8D3780FD-873E-499F-9135-74E87942E5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0918f4cd43dca0eb076ecf258fc28905971dcc77","datavalue":{"value":{"entity-type":"item","numeric-id":4371686,"id":"Q4371686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$3C25AB01-305F-47BD-8423-80BF89304B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f442ad88543763a7485036316226ee23e07cc75","datavalue":{"value":{"entity-type":"item","numeric-id":5920702,"id":"Q5920702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$64724F7B-841C-4FDD-AF69-5EEDAB46DBF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24d071c0e63ccc4acf5f859969db29f7f9386afa","datavalue":{"value":{"entity-type":"item","numeric-id":1384530,"id":"Q1384530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$DBB3A5B3-6058-4522-815F-0DAE86FAB1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20c187cf9d1b3b43602f19734021f9ad7094c5de","datavalue":{"value":{"entity-type":"item","numeric-id":3002770,"id":"Q3002770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$2AE026F1-12B5-477D-B38A-6D0A3F709CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a540e9211b030f1510e3fc790a0ead96867357c2","datavalue":{"value":{"entity-type":"item","numeric-id":5305882,"id":"Q5305882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$7143E362-0FF3-427D-AF93-FB98A30090EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54a29adf8940202a7f55f502dff0d03c91fa5377","datavalue":{"value":{"entity-type":"item","numeric-id":4327633,"id":"Q4327633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$E7223B2D-876E-4EEA-9189-A6AE8610683D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26d46be8b98320ac11d9f89373b1b9bc29b64e0c","datavalue":{"value":{"entity-type":"item","numeric-id":1322465,"id":"Q1322465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$F1635348-B839-4CF8-8A62-F9F2005DA825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49172515abb1787109c970b5001f0a76a4d18de1","datavalue":{"value":{"entity-type":"item","numeric-id":4277547,"id":"Q4277547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$B006626C-3626-40F5-ABF7-5D7EB8E10B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2daae0bb83cad646c82bd4e30eaf4258cdff2c05","datavalue":{"value":{"entity-type":"item","numeric-id":3140018,"id":"Q3140018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$F506A414-B6B0-4B7C-AF23-770CAC07E342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93102dc9c5454b4e87e550298f9d68a170764862","datavalue":{"value":{"entity-type":"item","numeric-id":4839061,"id":"Q4839061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$0897BA16-437A-450E-9913-CA479056ABAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc125b9d0451994663c708da31405626b2ebc3b8","datavalue":{"value":{"entity-type":"item","numeric-id":4431436,"id":"Q4431436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$63112606-1373-4459-8825-64ACFD770D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$691D8E54-61FC-4D75-9A2B-79D71FD8D764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34866ea766971af89b30adf0e5d6c644f933a12f","datavalue":{"value":{"entity-type":"item","numeric-id":3813320,"id":"Q3813320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$0F19DFAD-2AA4-453E-B026-FC3BD43B6B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d52dacd006714a1235fb482048cef635e725552","datavalue":{"value":{"entity-type":"item","numeric-id":1969435,"id":"Q1969435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$082D0F5A-5F4E-47DA-8FFC-107936A10DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be9bd0980ca6d0ed5ae6509ecff0a7505f5fbdca","datavalue":{"value":{"entity-type":"item","numeric-id":5172697,"id":"Q5172697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$E8798E7D-D574-4A77-B041-7E6D986123EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"487d70ff05b105884061ed5021816f90ad11fb91","datavalue":{"value":{"entity-type":"item","numeric-id":1881232,"id":"Q1881232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$1A8FADB6-2E04-4B19-B77F-B95CB6211335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a4339f157b5db47124df1e48c6422ab87d6805d","datavalue":{"value":{"entity-type":"item","numeric-id":3714486,"id":"Q3714486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$FA677671-E540-4AAC-B89C-AD00FB5A9702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1278dfd796d6cf90ae811a6ff576c660ee7f17d3","datavalue":{"value":{"entity-type":"item","numeric-id":4247017,"id":"Q4247017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q628302$CC4A26B6-67CE-48EE-80CB-5CAE344DE9A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8613b4bb03fcff43d2d21a8ca5426c89cd039277","datavalue":{"value":"10.1016/J.DAM.2010.08.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q628302$29511FEC-0ABD-4AFA-AF45-2DE2FD47B284","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3d80212dc73da00c54665ab2c57cd51979e7a35","datavalue":{"value":{"entity-type":"item","numeric-id":3541814,"id":"Q3541814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a48f7f9dca9a48494398a1382ad4d1279208d69c","datavalue":{"value":{"amount":"+0.9663822650909424","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":"Q628302$C595321F-403D-4B31-A21B-21247BD13757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0bafa2130f303bd8f87bfc5e31f40602552015d","datavalue":{"value":{"entity-type":"item","numeric-id":5479382,"id":"Q5479382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fe38d4a49295e54a085d3966bac114ee5ad7358","datavalue":{"value":{"amount":"+0.908334255218506","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":"Q628302$3107825A-6D4D-49C6-9CE5-54C63C547A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee3605b080a27236a4b564be046a0255e8af9630","datavalue":{"value":{"entity-type":"item","numeric-id":3002770,"id":"Q3002770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57a90fd1522032002393cc115761a28cae39559a","datavalue":{"value":{"amount":"+0.9079965949058532","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":"Q628302$BFCCE323-B0D9-4A75-B73E-7DCED1D40ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f792e2e24c07800fd51621a52ba1bf46e40381a8","datavalue":{"value":{"entity-type":"item","numeric-id":3148827,"id":"Q3148827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5e321ff6ed536092660449ea43d84de454d17f2","datavalue":{"value":{"amount":"+0.8765711188316345","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":"Q628302$3FDE5C1C-7A12-48B3-BC9D-8EFBD769537C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a521b8519101aed8a35c99b72314125898d4cc47","datavalue":{"value":{"entity-type":"item","numeric-id":5172697,"id":"Q5172697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"130ffe8aa007f7a82e67be87341ed2da2504f89d","datavalue":{"value":{"amount":"+0.8732414841651917","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":"Q628302$535790EA-0449-46F9-A187-2863F7498C5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:628302","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:628302"}}}}}