{"entities":{"Q5944107":{"pageid":8120909,"ns":120,"title":"Item:Q5944107","lastrevid":47676361,"modified":"2026-01-02T09:58:40Z","type":"item","id":"Q5944107","labels":{"en":{"language":"en","value":"Complexity bounds on general hard-core predicates."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1652620"}},"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":"Q5944107$3556CFA0-FBBE-408A-9737-A24D32E07574","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0474914858cd77ead78746893bfb076ebbb231b0","datavalue":{"value":{"text":"Complexity bounds on general hard-core predicates.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5944107$19ABE416-A097-44D5-B6C3-361E982522A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7730025abe9f669fa169112eda1aed4730efff0a","datavalue":{"value":"1063.94073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944107$BA454E3F-79B8-4756-88C9-101317F6D428","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c84ea94fcb3220f1d93906d40fc87797c4581cc6","datavalue":{"value":{"entity-type":"item","numeric-id":204360,"id":"Q204360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944107$BB4C42E2-E846-441B-B0A4-82B3F89A73C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4465253b39c46c46ff053cab5b9a7cd7d50a386","datavalue":{"value":{"entity-type":"item","numeric-id":204361,"id":"Q204361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944107$54CD907B-5635-4373-B571-8E27ABC7E44E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e1640d7463d22bb99b71dc73dd0067db506b020","datavalue":{"value":{"entity-type":"item","numeric-id":204362,"id":"Q204362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944107$723B250A-271A-4A31-BB06-565FDCA1B589","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d5eab3bbb3b6673353b9ed770934b15d004ef795","datavalue":{"value":{"entity-type":"item","numeric-id":166358,"id":"Q166358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944107$7E642A52-5440-4B84-9A99-7984B3EE4EA9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6922bf4f48af58db065498669d85c0a2b89262a3","datavalue":{"value":{"time":"+2001-11-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5944107$28EE70C8-CE85-417E-B054-3C96B1FA8D38","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2241fc9cc94bc33f12309c47a2a47d107fc19d4a","datavalue":{"value":"A Boolean function is said to be a hard-core predicate for a one-way function if it is efficiently computable, but given the value of the one-way function, the value of the hard-core predicate is difficult to predict. The question studied in the present paper is how hard a function must be in order to be a hard-core predicate. A general condition in terms of Fourier coefficients is given that implies some previous lower bounds (e.g., hard-core predicates cannot be in \\(\\text{ AC}^0\\)) as well as some interesting new lower bounds (in terms of monotone circuits and threshold circuits).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944107$EFADDE46-8C26-4E30-B3F0-728F93E7D4D6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5944107$578A4332-9AF0-43C2-A8C4-9B7A5683CED8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944107$E79C9181-1F2B-4285-AD11-AE34C9AB435E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7329631d0ee4fc230774d9eb0001573244e2df93","datavalue":{"value":"1652620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944107$A2936BCA-7AFA-4755-A8BC-E80E974365A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944107$8F4BA298-2FF5-41E0-B1BD-250FB964EEBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9751e40fc64b559f097ced67cd2c8f328b9f12c","datavalue":{"value":"one-way function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944107$3DD2D70A-3D9E-4457-ACC9-477B7E7DC67F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d6fbd06d3e339fb2a2ba8506ad3e7270a982e3e","datavalue":{"value":"hard-core predicate","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944107$D4D86B6A-6A70-4A48-864F-4B25668E7C4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8c3f5b9a4eb462b5eaef09ca97763e21fd802c1","datavalue":{"value":"pseudorandom number generator","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944107$13E926BA-0B29-4A65-BF42-8C81734C712B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5944107$378C0EF2-22BA-4D36-864B-1F7E099D7B8C","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":"Q5944107$E7DB9196-9AD3-4559-9549-875A7797D3CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eaa5c1ce7fc051068544946b99bc3cfedfe34b9d","datavalue":{"value":"https://doi.org/10.1007/s00145-001-0007-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q5944107$63A3DED4-E33D-467B-BEFC-86258539250F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a2b10d06bd22e3f2f3f8e977629b58131cdcf0b","datavalue":{"value":"W1899845837","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944107$34ED2668-B276-4225-946C-384657A48B6C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"982e9893564e3cca592bad6d6f57b4a4274468e2","datavalue":{"value":"10.1007/S00145-001-0007-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5944107$28629801-F842-4956-8378-C4D6B7A19DCA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e3a8e0e6322df6f8ed359156af105a91bb5ef33","datavalue":{"value":{"entity-type":"item","numeric-id":4364539,"id":"Q4364539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e2b99c9e9fcc301aa4381a92e0d6183aa4bf485","datavalue":{"value":{"amount":"+0.9187295436859132","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":"Q5944107$B11B1EA6-E09B-482E-B5A0-6C8FF747BB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa212bb27640d0790e4e34467a4172761db04030","datavalue":{"value":{"entity-type":"item","numeric-id":4501567,"id":"Q4501567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5b891d7f5015ecd0f3a74d533b84e09914a7640","datavalue":{"value":{"amount":"+0.9107248783111572","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":"Q5944107$B8724299-E44F-4240-B7D3-A118F2CEA21A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"396254899a5d3a4327dec0ec31ddbac85dde6a8f","datavalue":{"value":{"entity-type":"item","numeric-id":3753481,"id":"Q3753481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5b891d7f5015ecd0f3a74d533b84e09914a7640","datavalue":{"value":{"amount":"+0.9107248783111572","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":"Q5944107$72819BBB-FD07-4A10-91A6-402DD52D3B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"429ef19b3ccb1637de1eddb8dd4ca3e76a066113","datavalue":{"value":{"entity-type":"item","numeric-id":5311559,"id":"Q5311559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b4524c045d8d25ba9841ccf971f6032b1613415","datavalue":{"value":{"amount":"+0.7923688888549805","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":"Q5944107$D4F07359-CE08-4D47-AF25-EDCE87953B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ada3dad3fe568e116be584efde849b895e64485","datavalue":{"value":{"entity-type":"item","numeric-id":5428808,"id":"Q5428808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76c0f7d8de2f26b5c7087f6a181ab60ce5441341","datavalue":{"value":{"amount":"+0.7906434535980225","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":"Q5944107$4E5B7194-03EB-477D-86E7-5230083A414F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5944107","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5944107"}}}}}