{"entities":{"Q428873":{"pageid":430640,"ns":120,"title":"Item:Q428873","lastrevid":61766106,"modified":"2026-04-11T01:31:28Z","type":"item","id":"Q428873","labels":{"en":{"language":"en","value":"On derandomization and average-case complexity of monotone functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6049393"}},"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":"Q428873$5AAA48F5-49CA-46ED-A2A4-55075BA6445E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7d5a824008df260bd37bdebfcb0bb22dde3073db","datavalue":{"value":{"text":"On derandomization and average-case complexity of monotone functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q428873$217EE5BB-09E1-4B86-95FE-C96694DFD307","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b7c4f3909c617215be268091e723fb960f47546c","datavalue":{"value":"1251.68119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$85C08328-AE54-4D65-B35E-7D8D71482984","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c53410e8a98da0f2a5a5c73405c2f6e4d3c4c5ef","datavalue":{"value":{"entity-type":"item","numeric-id":428871,"id":"Q428871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$6F860E07-AB29-4540-9F76-F8B8C46B6558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1461943fc7095eec35aba57d08a62c688b37413","datavalue":{"value":{"entity-type":"item","numeric-id":428872,"id":"Q428872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$124403B3-4F23-46C0-9FFF-F89F329C24E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a25d963ba8459ff509d0f0ec3595c17b9f7f836","datavalue":{"value":{"entity-type":"item","numeric-id":354650,"id":"Q354650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$FFB7EE20-4413-4CFA-9634-CEA32E2DC0D7","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":"Q428873$B83262F4-B06B-47B4-B80F-1EDF6E59BBD0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f72164bd681bf7e905e9de5f982349bc17f0310f","datavalue":{"value":{"time":"+2012-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q428873$62E6F819-7065-45B1-A938-4EA7E0AEC157","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$260E062A-EAF5-423B-BE1E-40AEE1D33270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$1B7B4AB8-53E2-49FD-87D2-6AE25139577F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$2D25AB97-1705-4EEF-A986-5205D8584981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$17EE3CF5-27C8-474F-8C7B-012E40321131","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b1393f449b1aa480fdfb3a42fddb1065135cdb99","datavalue":{"value":"6049393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$1B9624AD-7F75-401E-B84E-0FC469A88663","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q428873$2B900688-29E1-4752-82FE-A22CB81C6606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3eb65725d343868a6997f8adadfcdfa29f4c5fe","datavalue":{"value":"monotone circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q428873$C6C995C6-58D2-4E06-9EA8-CB2E78290283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6178e6e3ee3ad49e11d737a882d76361265c248","datavalue":{"value":"monotone functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q428873$CA0E8A1E-8C62-4680-BF36-100A82B4C77D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q428873$9155E13A-1C13-44D5-8089-42E8D663B449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"797ca31b1acf5bf389b0a92a7ae49cb449b952fa","datavalue":{"value":"pseudorandom generators","type":"string"},"datatype":"string"},"type":"statement","id":"Q428873$D4D6A769-4FB9-4055-8516-A576E69F8B2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeb5cf5222b6371fb7f9c168c78eb205663c9be7","datavalue":{"value":"average-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q428873$780C79FF-7356-4B78-B413-C440F29BB75B","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":"Q428873$C714FD1F-35BC-4C6B-90E7-109DCE56A1EE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce455517db2ae0dcfdaba31683dd2864b452eca8","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.02.017","type":"string"},"datatype":"url"},"type":"statement","id":"Q428873$88E56950-3299-4422-9095-8181D54ED479","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c77dd722d676cb7c716713dd3f7cd87c9ff100ba","datavalue":{"value":"W2047406446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$8BEA8ABB-7CAF-4B5D-A5A5-BD8409AA1371","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8653d2e6f53b17cedec7b9470bcf88609d4f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$44FC65B0-5579-477F-9C1E-97287D70F955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654f40fbfc6c0b79882eb67b58f7af341fb43aa3","datavalue":{"value":{"entity-type":"item","numeric-id":1390872,"id":"Q1390872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$92E99F0D-E07A-4A7C-94B6-AA11E50B513C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9208528a9398d42022a83d3910fdcc8477ab6c6","datavalue":{"value":{"entity-type":"item","numeric-id":2784326,"id":"Q2784326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$DF6B2562-CC73-423C-9146-DB380559642D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b87d4d660be017ed3a655c9578140dd400c43c7","datavalue":{"value":{"entity-type":"item","numeric-id":4385519,"id":"Q4385519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$293B4308-78BC-4820-A8E8-E60A6C91F131","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":"Q428873$61F32263-DCEF-4B52-8B90-98E9BDA075C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fee22198e629ab0ee2299a3bec1c5cbc51a36698","datavalue":{"value":{"entity-type":"item","numeric-id":3652295,"id":"Q3652295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$066BA245-A1DC-4F99-BD1E-4F9B84851DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"509e452b6dd0f8e036244daa5f6ac10d798d6bd2","datavalue":{"value":{"entity-type":"item","numeric-id":5916126,"id":"Q5916126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$03F24524-8195-482F-A2C6-DE5EA6895418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f59bf1f643a8f16cffedaf1e53043ff000e62ae2","datavalue":{"value":{"entity-type":"item","numeric-id":626680,"id":"Q626680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$9A8A9AE9-BCEB-4926-B845-1909FDD2ADDA","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":"Q428873$6F7A8ADC-98C9-4C38-B19B-E8732505CA32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65bda7992854c005a2d41053960e3d7c71a702f6","datavalue":{"value":{"entity-type":"item","numeric-id":4829648,"id":"Q4829648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$6E522434-017A-4F0E-9C28-DF76D6E147F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29fef0cb8ad9a782cc9919c5583879e79345971a","datavalue":{"value":{"entity-type":"item","numeric-id":4788614,"id":"Q4788614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$A4188762-560A-41A1-AB1B-614B8F0BCD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c8370a62220455086d6e5eaccb93619f2288af3","datavalue":{"value":{"entity-type":"item","numeric-id":4938667,"id":"Q4938667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$77DBE813-6872-4F2C-9F30-3067713250F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b409306bdf364930adcbf624496cede43048b2af","datavalue":{"value":{"entity-type":"item","numeric-id":1337458,"id":"Q1337458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$C418569D-F61A-4E20-AA95-B1DCEA7D986B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a53db3e7d6700de9e42fc48a29bd259b2c12ae64","datavalue":{"value":{"entity-type":"item","numeric-id":5917544,"id":"Q5917544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$DB237019-7868-4635-A06B-BE1893DE192E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e822d0f6871d5df9de9fd97a15be05d850e629","datavalue":{"value":{"entity-type":"item","numeric-id":1071001,"id":"Q1071001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$F4E0D7D7-4A08-49A7-B55B-BC206B54C0AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9b6d408d87a26b1fc430614787ab8e2ccfe79d9","datavalue":{"value":{"entity-type":"item","numeric-id":3546310,"id":"Q3546310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$543EB380-78B7-473E-B35C-4F9EBB6F0B95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b2e8fdbd72d4413672bdc0a2c0dcc9057a5f41e","datavalue":{"value":{"entity-type":"item","numeric-id":1813126,"id":"Q1813126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$D3CB6C44-D52B-408C-8C3F-9BE559AE54EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6be260040de79846258d2a06bc67ff95051f5a1f","datavalue":{"value":{"entity-type":"item","numeric-id":5917585,"id":"Q5917585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$DF2A313E-3573-4B08-BE47-CA3315E64918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e06cd08b21ba41692bb65b88d6aafecf32e6a8","datavalue":{"value":{"entity-type":"item","numeric-id":4726175,"id":"Q4726175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q428873$346EC0DD-7551-4BEA-9BF3-A7B99775B090","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28a0a4b6b8e2b1baba40cc9e8ef70b01339bd4a2","datavalue":{"value":"10.1016/J.TCS.2012.02.017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q428873$10068069-C3D3-4539-AA02-D2B972EFF61C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f5c2bbac209cd30585af1846d105ba0db13f892","datavalue":{"value":{"entity-type":"item","numeric-id":2931400,"id":"Q2931400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de26bc56d79f6709e2ffcbd292c47b1806204bf9","datavalue":{"value":{"amount":"+0.8024932742118835","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":"Q428873$86428A7A-142C-4CD7-B655-C00189EC8739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44d5d7379b5a8823f7a17f36fa62ab11dc4688be","datavalue":{"value":{"entity-type":"item","numeric-id":2913810,"id":"Q2913810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee85adbbda052414e5f1d389471e7ee23d02dbd2","datavalue":{"value":{"amount":"+0.7973721623420715","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":"Q428873$96B8B71D-143C-45B4-9854-86F8AE53268D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4c15152bc6e04c1b2d97a8e08ab10931556ffd6","datavalue":{"value":{"entity-type":"item","numeric-id":3578298,"id":"Q3578298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"544d41be2defaf6bf9116dc8676396e87e5248f6","datavalue":{"value":{"amount":"+0.7890397310256958","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":"Q428873$38160BE1-B4DE-403A-8A2C-FBEAD00C5078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a46550f586461cc671fe772038e085d47a31254","datavalue":{"value":{"entity-type":"item","numeric-id":3084685,"id":"Q3084685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f325522dba955c7623461a8527d24a930e7e67f","datavalue":{"value":{"amount":"+0.7887293696403503","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":"Q428873$1D3D73E7-A0B1-4E23-96F4-5E2D08826696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a149c0fd97e674a30d7f27a3d3158da13031144","datavalue":{"value":{"entity-type":"item","numeric-id":1675542,"id":"Q1675542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abebfe6c28b4f1eb29da9d2df4a4734347bfd5aa","datavalue":{"value":{"amount":"+0.7772853374481201","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":"Q428873$A9716004-EA3B-4070-A53B-13F2B4615D43","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On derandomization and average-case complexity of monotone functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_derandomization_and_average-case_complexity_of_monotone_functions"}}}}}