{"entities":{"Q6581789":{"pageid":14192944,"ns":120,"title":"Item:Q6581789","lastrevid":95787485,"modified":"2026-06-05T09:46:07Z","type":"item","id":"Q6581789","labels":{"en":{"language":"en","value":"On one-way functions and sparse languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7890220"}},"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":"Q6581789$8ABF4E30-BDA7-426F-9970-2C2CCF609879","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"112273b5f6485ad73b818fce7aed6c43f7b27224","datavalue":{"value":{"text":"On one-way functions and sparse languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6581789$DB53F072-638D-4C80-8920-AE222C0ABE95","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c869413bea7937d3251237aeb91e9c0f51522b8","datavalue":{"value":"1544.94197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6581789$7B659AD3-9B80-42F1-A174-09E59B771178","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c28267e604eb8ae19925f935f3fdf3e47d738771","datavalue":{"value":"10.1007/978-3-031-48615-9_8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6581789$0D18D2F5-0DAB-41A2-97D4-5950B7E31540","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e092785eb7442d24838d88e07b8abf6008f78e9","datavalue":{"value":{"entity-type":"item","numeric-id":2119052,"id":"Q2119052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$60CE7659-9E87-4C7C-A810-0C3ABFAD044B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fb4d7c30f1ec1e2805a68412329b686fb2c16d4","datavalue":{"value":{"entity-type":"item","numeric-id":332269,"id":"Q332269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$B70180C4-922C-4068-A5FB-62C1C37079AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"93497291d8ba3cd4ceda2bd397bb8743ea86f872","datavalue":{"value":{"time":"+2024-08-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6581789$9AB53D16-3522-4C33-B1BB-236E9394B915","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"34cd2735affccf7ac01cb9a6fddca41a2a7a8b3e","datavalue":{"value":"The authors show the equivalence between the existence of one-way functions and the existence of a sparse language that is hard-on-average w.r.t. some efficiently samplable ``high-entropy'' distribution. In more detail, the following are equivalent: the existence of a \\(S(\\cdot)\\)-sparse language \\(L\\) that is hard-on-average with respect to some samplable distribution with Shannon entropy \\(h(\\cdot)\\) such that \\(h(n)-\\log(S(n))\\geq 4\\log n\\); the existence of a \\(S(\\cdot)\\)-sparse language \\(L\\in\\mathrm{NP}\\), that is hard-on-average with respect to some samplable distribution with Shannon entropy \\(h(\\cdot)\\) such that \\(h(n)-\\log(S(n))\\geq n/3\\); the existence of one-way functions, where a language \\(L\\) is said to be \\(S(\\cdot)\\)-sparse if \\(|L\\cap\\{0, 1\\}^n|\\leq S(n)\\) for all \\(n\\in N\\).\\N\\NTheir results are inspired by, and generalize, results from the elegant recent paper by \\textit{R. Ilango} et al. [STOC 2022, 1575--1583 (2022; Zbl 07774439)], which presents similar connections for specific sparse languages\\N\\NFor the entire collection see [Zbl 1542.94005].","type":"string"},"datatype":"string"},"type":"statement","id":"Q6581789$79715FD0-2C47-4C05-8329-4EBFA158AE1B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9653bb6f4ba3e8a4af13e520bbf2c05481477e2","datavalue":{"value":{"entity-type":"item","numeric-id":1616872,"id":"Q1616872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$B97C4CE9-1E2B-4D8B-9EDB-1C00542B8664","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e30d62051793251cdb7305d492b252b2239dfb5e","datavalue":{"value":"94A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6581789$C422E0FC-30B6-4E02-B89D-855D6513F0BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6581789$E3BE2F4E-23C8-4B54-97D9-4BB5FAB6731C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ced44d76ec9d8752fd115b26a741fa9937b0b972","datavalue":{"value":"7890220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6581789$222D54B8-255A-4B72-A728-B036ED8B46DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a2b24f6056a67bc35da06909c9272de4feab241","datavalue":{"value":"one-way functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q6581789$8B71808B-C238-4474-979D-4A8818D82BD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5448ee1e5e56b7b0d957feda10918c894ca18ebb","datavalue":{"value":"sparse languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q6581789$7FFA1E2E-5E7C-4002-B28D-AEADC3347A38","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":"Q6581789$0938904F-84B8-405A-8C31-3754274D2F78","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a581f96e8cabd60b98280dbc93b840cb31eb7421","datavalue":{"value":{"entity-type":"item","numeric-id":3339289,"id":"Q3339289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$5FE1B957-6A8A-49BA-AF8A-9F91940E8606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e40651885e589ae16736b2ed26430168a8207418","datavalue":{"value":{"entity-type":"item","numeric-id":3875826,"id":"Q3875826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$DCA43530-432F-480E-8221-F16869269639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c94b5f6d1224b677c93bebd7a34b796c6eb51370","datavalue":{"value":{"entity-type":"item","numeric-id":2974488,"id":"Q2974488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$3CE89B4A-DC5C-4E9D-BEDF-ADEEAB9F140F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b548fb76f8ef8a56f9223030f407f1a96f0c7ba1","datavalue":{"value":{"entity-type":"item","numeric-id":1057832,"id":"Q1057832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$B2CF5FB5-9155-479E-A8EB-AF7E1C2B25F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe813ef57b4e6c758bcf1f841c41c79d71435de","datavalue":{"value":{"entity-type":"item","numeric-id":4712666,"id":"Q4712666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$D087D569-761A-410F-911B-846A34BE9363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454365720643dfded828f337324cf7a01ad906df","datavalue":{"value":{"entity-type":"item","numeric-id":4268715,"id":"Q4268715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$B6E73828-D027-4F47-812F-1BB041A56F4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8c486b42986d64260af68812bf4cf235fad3fdb","datavalue":{"value":{"entity-type":"item","numeric-id":6083613,"id":"Q6083613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$1D16257B-F323-4D55-9CEE-9F36C00C958A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6841b9962aaa0960cd814a5370c9e0eeb2fc6839","datavalue":{"value":{"entity-type":"item","numeric-id":1091817,"id":"Q1091817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$CC2868F7-FF78-4822-8556-D1A8FBE655AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4673e71a7d4faf27e474d74b82d0985b6024b624","datavalue":{"value":{"entity-type":"item","numeric-id":5558743,"id":"Q5558743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$A19ECF95-8B22-4ED5-9AC2-006FBDF8EDDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e693e7ba2ef3d9aab35688170a4cfe82fbed8532","datavalue":{"value":{"entity-type":"item","numeric-id":2487080,"id":"Q2487080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$52FF4396-F4D7-42E2-A8F0-23FFDBD62C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d572bbcf304ce2581911e61fffee94ad55ab61d","datavalue":{"value":{"entity-type":"item","numeric-id":808241,"id":"Q808241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$8F0B8B25-D25D-4D23-BFB9-566B2A391DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80187e65c3d02218a1c1b84468898391dd828b52","datavalue":{"value":{"entity-type":"item","numeric-id":4145254,"id":"Q4145254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$348D54D8-6707-4D11-BDE4-9F2F4E2387A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14efb49139bf6636efc61d26092213d1072148b8","datavalue":{"value":{"entity-type":"item","numeric-id":4779250,"id":"Q4779250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6581789$6DC4B351-42A9-4883-9601-6B5D54D09162","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bef85636703b6c954d75ffefce7071f4cd4594c","datavalue":{"value":{"entity-type":"item","numeric-id":2170063,"id":"Q2170063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa17234c0f89f55a9157c9ab4b67ed568db1999b","datavalue":{"value":{"amount":"+0.7526488900184631","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":"Q6581789$784F80B9-348A-480D-892C-6B6533D268CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff174ac439be7c7b749ddc83cef7b2c570e2d9bc","datavalue":{"value":{"entity-type":"item","numeric-id":1096587,"id":"Q1096587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f1435a148c1225d9209c866778f578c31c20322","datavalue":{"value":{"amount":"+0.7514070868492126","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":"Q6581789$EB2162C7-4D88-44A2-8AF5-DDB01F3BE2EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a77fba4c5f7f719f4e935cab767e6adce0d02bc","datavalue":{"value":{"entity-type":"item","numeric-id":6665547,"id":"Q6665547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf13530f08e4f08843a3f26f14ea507e6e2d1f0c","datavalue":{"value":{"amount":"+0.7496019005775452","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":"Q6581789$B39A2627-A1B1-4DC3-9486-6687305BEB3B","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":"8845db83a1819030993adbc17fd1408b7801e6ad","datavalue":{"value":{"amount":"+0.7495806217193604","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":"Q6581789$123C0B57-6C7A-4FEA-833B-17A00F40AAD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68666d51c81a7dd58379ed206ce2b0b20f237ecc","datavalue":{"value":{"entity-type":"item","numeric-id":4205082,"id":"Q4205082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d34a6bdffd331abd74061ed96ac8170925a72099","datavalue":{"value":{"amount":"+0.744827389717102","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":"Q6581789$8FC2901F-D73D-46FF-A2E7-EC5552DA3F5A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On one-way functions and sparse languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_one-way_functions_and_sparse_languages"}}}}}