{"entities":{"Q1094137":{"pageid":1104889,"ns":120,"title":"Item:Q1094137","lastrevid":66121482,"modified":"2026-04-12T07:41:28Z","type":"item","id":"Q1094137","labels":{"en":{"language":"en","value":"On using deterministic functions to reduce randomness in probabilistic algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4024788"}},"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":"Q1094137$149A22A5-10C7-4236-86B4-DF1D1E281527","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"76c5eafa10a233eaacd00c18eb8c472b590db21c","datavalue":{"value":{"text":"On using deterministic functions to reduce randomness in probabilistic algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1094137$CEF5D72C-981F-406A-9833-0F1005F7C197","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e40ea0f7bb325696c97efc155437b7823facf50","datavalue":{"value":"0629.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094137$DC7B90AD-0AF8-475A-B95A-BF875EF80D9F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"56e670155c82ad3d6395f1c3a3cc62959d85e8d2","datavalue":{"value":"10.1016/0890-5401(87)90023-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094137$41E39570-478F-4176-8343-3232A4ADB0F9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"195a11023b9fa51026b0ae4c10238ff0a353371b","datavalue":{"value":{"entity-type":"item","numeric-id":407593,"id":"Q407593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$370CCF70-F875-49B0-8F27-629C213840DB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$BED65A85-994D-4D20-825E-AFC84C432628","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1094137$EA3033CE-F58D-41DE-8B12-A6D2E9A55171","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"499e8b9e3150a4db59acfe98afbb3444098a9bec","datavalue":{"value":"We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n/2, and s random points, it is possible to generate deterministically from them \\(s+k\\) points such that the probability of not hitting the unknown set is exponentially smaller in k than \\(2^{-s}\\). Tight bounds are given for the quality of such schemes. Explicit, uniform versions of these schemes could be used for efficiently reducing the error probability of randomized algorithms. A survey of known constructions (whose quality is very far from the existential result) is included.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094137$7BAF8E49-6603-46C8-A31C-276A684FD165","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094137$3920868E-6669-4D7F-B9BC-D5BF26E6F1E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"644168861563d744992598872889acc4d8642a23","datavalue":{"value":"4024788","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094137$8CB0399B-E67B-49FA-A135-638767B7D4C4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b75d02aa96eefe42964c24b2e52964b9dd69149a","datavalue":{"value":"sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094137$12FCCD58-1A92-4E93-B8FA-F410B22438C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6deca9b5ebc941b9361ce3a1c641ad2e809f90e6","datavalue":{"value":"error probability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094137$15F73064-42F4-44C8-B66C-6E45E28C1DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49eb4dac5aeb1a5fd4804122c81f369b6968def6","datavalue":{"value":"randomized algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094137$D08F2FA4-C63C-40D8-B324-C1956A16B0CD","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":"Q1094137$5F9027A3-99AE-48C6-A5A6-E1B7E5374F2C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ab44c38234842ff7992ba00e47b9713793ea09","datavalue":{"value":{"entity-type":"item","numeric-id":3782808,"id":"Q3782808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$6370770A-0D04-49CB-A970-D4E2E1B1C044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b729bbd6e61b662781ffb74f80a3e1dd1a8250d","datavalue":{"value":{"entity-type":"item","numeric-id":3738458,"id":"Q3738458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$91F4D75E-F3C5-4F0A-92BE-81C10DC807F4","rank":"normal"},{"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":"Q1094137$B1675AF8-70E5-4268-8934-5C59F28F84B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c370940f88e260ea9c75b2735c4be0912a6727","datavalue":{"value":{"entity-type":"item","numeric-id":3205169,"id":"Q3205169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$5E9D0DF2-7EC5-496C-958E-C6DF3D882181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4031ba4150b815a0e72c8d690cf0ca1d9a241f41","datavalue":{"value":{"entity-type":"item","numeric-id":1098859,"id":"Q1098859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$CA3AE732-02A0-4F12-8602-7AD10947D768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4889dc56c7217c646e3175bcede965add157ef74","datavalue":{"value":{"entity-type":"item","numeric-id":4134003,"id":"Q4134003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$84CF9299-29D5-4FC5-BADD-17B8B92D76F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c124b23e66bda5f6b96b58b4ca724e8f07b76603","datavalue":{"value":{"entity-type":"item","numeric-id":3229522,"id":"Q3229522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$D43113C4-2484-49F0-A74B-46A5FA84DFB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0c28d649480a64fe8862189f4dca6ec55e2d05e","datavalue":{"value":{"entity-type":"item","numeric-id":3745279,"id":"Q3745279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094137$D47F6D61-AE77-4F54-8F95-BA02732BE482","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d94f6e934d7e93d39c832b94022851c44f5b22e6","datavalue":{"value":{"entity-type":"item","numeric-id":926181,"id":"Q926181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ee26d4678e8f6d393508d0c4eda889b153fa8bc","datavalue":{"value":{"amount":"+0.86788386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$DBC12BD6-1DCB-48DA-B5D1-C136CE50E0F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f841d1ed1202eb522372d5935282f6a4de658957","datavalue":{"value":{"entity-type":"item","numeric-id":6087001,"id":"Q6087001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b43a724e33c79ee2e05244f96a36455333cae6d1","datavalue":{"value":{"amount":"+0.8598658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$5F14733F-C5C8-4F62-A881-54C54CE4D7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3416da6aa75011bcbdaf43ac03bd75a70131f7e5","datavalue":{"value":{"entity-type":"item","numeric-id":5300079,"id":"Q5300079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"497c1779cc23a7d16b7dc72e3022f4448fce7315","datavalue":{"value":{"amount":"+0.8543608","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$F9FB2EC6-8E4A-4987-A142-FC3B6F015BE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dde4598d05d0cac1254841c4b0f333732b9cb765","datavalue":{"value":{"entity-type":"item","numeric-id":3345786,"id":"Q3345786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22637c0a4e8880ab4b41f36229ad546860f67908","datavalue":{"value":{"amount":"+0.8535463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$2A436E06-3047-448E-AD62-BB4D2A5774F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f4a8a98ee07fd2097fa8c2bac6dbcdd29624d19","datavalue":{"value":{"entity-type":"item","numeric-id":4961126,"id":"Q4961126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74b4e97b9c595bcdebbc2659c3edd6786dcbf8c9","datavalue":{"value":{"amount":"+0.85039985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$000E6716-0ED1-4B3C-9EC7-8B6E5B5E6622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d81bba91d0fa657bb624f5886baf8f8edbb32dca","datavalue":{"value":{"entity-type":"item","numeric-id":4630263,"id":"Q4630263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37865273a0bc8c2b88ace4a394313e5c45ee23fd","datavalue":{"value":{"amount":"+0.8487839","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$E670A1B0-A52D-4FF8-BAB2-7DEF26F417B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afe386459c80115949dd423bfb96e042dead5205","datavalue":{"value":{"entity-type":"item","numeric-id":1365675,"id":"Q1365675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37865273a0bc8c2b88ace4a394313e5c45ee23fd","datavalue":{"value":{"amount":"+0.8487839","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$1C8677A7-4884-47D5-AAF7-2C2858AED7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b14f1da409933b304bf9cd5129cb93616f5fffc6","datavalue":{"value":{"entity-type":"item","numeric-id":3825842,"id":"Q3825842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"082afeb581429aa2479796ba7d6633cf97acbd4a","datavalue":{"value":{"amount":"+0.848155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$EFA4D9FE-BA5A-40B9-AE9F-203279AEE87C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaabcdf394b8cdeff41fef9c3e867390604e6fbd","datavalue":{"value":{"entity-type":"item","numeric-id":1882527,"id":"Q1882527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11d59f089f7c5317a8fe3fa19a60f6e2731986af","datavalue":{"value":{"amount":"+0.847658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1094137$789B8573-6401-4D70-A47F-F44FE704746A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On using deterministic functions to reduce randomness in probabilistic algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_using_deterministic_functions_to_reduce_randomness_in_probabilistic_algorithms"}}}}}