{"entities":{"Q5862347":{"pageid":7891898,"ns":120,"title":"Item:Q5862347","lastrevid":55932523,"modified":"2026-02-21T06:49:16Z","type":"item","id":"Q5862347","labels":{"en":{"language":"en","value":"A polynomial-time construction of a hitting set for read-once branching programs of width 3"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7485830"}},"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":"Q5862347$0846F8B7-9D6D-4F2C-80BD-E540B37078CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b2b86296f2c1b6cbe6f97dfd8e4939435c46f52","datavalue":{"value":{"text":"A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5862347$17462424-A545-4B3D-99BD-C93580F8D975","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"87b569d42ed71e8e7fa841c2c512e6051e4f5474","datavalue":{"value":"10.3233/FI-2021-2101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5862347$22FF3882-81A1-4315-A350-3FD089FA12B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"628ffd0405f8e483f9a030da2f05c119b56abfe2","datavalue":{"value":{"entity-type":"item","numeric-id":1426459,"id":"Q1426459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$BA23FEBA-23D0-45E4-9B4F-390E5BDE9B70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac194c8415729c0b069bd70e642b567c974b0dcf","datavalue":{"value":{"entity-type":"item","numeric-id":593779,"id":"Q593779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$6CB7F225-92AC-4138-92BC-6F6215933806","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1529db038bde6a8aed76ac5e8432917aee1a9200","datavalue":{"value":{"entity-type":"item","numeric-id":2803574,"id":"Q2803574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$50AC0181-7335-4231-A788-A174428FFA71","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"acee27211c540e6d5c2366514874b0c468da47fb","datavalue":{"value":{"time":"+2022-03-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5862347$4D15D68D-1AC4-4F0B-B7F7-C9608E086AB9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"db64e3cc79ecd41b2e621540c12c9f061f696a28","datavalue":{"value":"https://arxiv.org/abs/2101.01151","type":"string"},"datatype":"url"},"type":"statement","id":"Q5862347$9C2E2FDA-8CEC-4641-8A0A-6B88B96DAEF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"62a49b155c9af634e6c3562b1547da1f7c08791a","datavalue":{"value":"68-XX","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5862347$F499D684-36C7-4709-B8E0-FCE43EAE1DEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5c7aa1ed25b0db7c77f8704f79f36587740e735","datavalue":{"value":"7485830","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5862347$1D98BA27-9A20-4FCD-9204-ED65CBA9711A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5862347$7A5C1DDE-9CEE-46A0-8D5E-B4B9B6476A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4282d5db6721a0519f4f520381157fa14d63ade","datavalue":{"value":"hitting set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5862347$A10E0010-5542-4306-B702-D1FFA5F9A793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad37d71a040074748b834ec8d9584eea5880ccb0","datavalue":{"value":"read-once branching program","type":"string"},"datatype":"string"},"type":"statement","id":"Q5862347$52998792-EE75-47AC-A518-ED9E12275DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789311983b62db7229ee55cb1e9f6ddbc5cb9513","datavalue":{"value":"bounded width","type":"string"},"datatype":"string"},"type":"statement","id":"Q5862347$DBF7C8C4-B6A4-4885-8BD4-67EE3832512A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96d50f690105c6c88dc66696d3d161b6a5a7f935","datavalue":{"value":"almost k-wise independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5862347$263183A3-3F6A-4062-BEEE-9AA6B16D4F62","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":"Q5862347$8DCE5C99-AD69-45FF-9619-4B6B3CADD2BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0261ff4d1792388f5ec3c51626109696a158e78","datavalue":{"value":{"entity-type":"item","numeric-id":1301514,"id":"Q1301514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$47C7AF62-50EB-4A63-8CCE-00624B4F4D2C","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":"Q5862347$E4DA069F-9115-4535-B512-60D29F407B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ee9bdbd9786926088840fd488fe60b509eb451c","datavalue":{"value":{"entity-type":"item","numeric-id":4485697,"id":"Q4485697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$BDAD500F-BF17-44CE-8279-4A48F41B4638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fdcedcbf4fcfe699f5f24c51d96bf9ae032cd7a","datavalue":{"value":{"entity-type":"item","numeric-id":1204523,"id":"Q1204523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$76F9D68F-6794-4309-8F38-77234ADE0AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aa10f8df6b40d0adf388f45531b9a211662db6d","datavalue":{"value":{"entity-type":"item","numeric-id":3191575,"id":"Q3191575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$9BED62D1-3520-4DF3-9173-15C140DDA990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23ae6c57cf96fa94139c2ace725da4e56c361094","datavalue":{"value":{"entity-type":"item","numeric-id":3191596,"id":"Q3191596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$2824E6A0-C869-48DD-9F09-0F51B8276CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0dbae47fecf2d793d44c3938ae7c9749eb086cd","datavalue":{"value":{"entity-type":"item","numeric-id":3190691,"id":"Q3190691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$526ADAD9-1AA0-4422-8640-3FD41C2FD01F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f087a8838156061f170b9edb2f70f769710e442","datavalue":{"value":{"entity-type":"item","numeric-id":5419096,"id":"Q5419096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$F1B8030B-A62C-4717-9B2A-AF0AECEBCF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e816bab1322d262b83f0111f0c59c447e4b2b1e7","datavalue":{"value":{"entity-type":"item","numeric-id":5448802,"id":"Q5448802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$802A3963-9DA1-49F2-AFB4-CD20F7956B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d44d594158b46d7626257750a29857255d94a89","datavalue":{"value":{"entity-type":"item","numeric-id":3588430,"id":"Q3588430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$937593F0-C8D9-47B1-9643-537F4EDDBB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09a3c4a236e1a86a9306468a70629484f76019f1","datavalue":{"value":{"entity-type":"item","numeric-id":4014640,"id":"Q4014640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$F0B2D64A-7A48-47CC-A283-8463ED321BAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d1fad59f100d44a225dd591778ef7145ede8f90","datavalue":{"value":{"entity-type":"item","numeric-id":2891385,"id":"Q2891385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$D9D9117E-3308-482E-B2C7-175E0B16E10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b16d300ed6a2362d85e7631ffdfa241212488f99","datavalue":{"value":{"entity-type":"item","numeric-id":3007622,"id":"Q3007622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$E8F102C6-7E7C-4622-B335-0EC9329D6FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b343b53a83c46a7848a05af7f6d11acf709ffbcb","datavalue":{"value":{"entity-type":"item","numeric-id":2851892,"id":"Q2851892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$730D94D6-F058-4D9D-AA81-C20273C3B4AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a65ab370e9fed42d94435ceb9ac84de21508b382","datavalue":{"value":{"entity-type":"item","numeric-id":395607,"id":"Q395607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$B6211C90-7E44-4815-94DB-F31DD6EB958E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d3b6b8140485c76824b66170ddfc0272eaed549","datavalue":{"value":{"entity-type":"item","numeric-id":5259623,"id":"Q5259623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$F562A61E-0038-43FB-A253-EE01040E613F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212b74299e52e5cd01ad7c3b2eb5698ee6bab936","datavalue":{"value":{"entity-type":"item","numeric-id":519906,"id":"Q519906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$CB901C98-198A-4415-B95B-0AACA03F7A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb68da4cd567b3249cc9010d2f609eb6bf03ec8a","datavalue":{"value":{"entity-type":"item","numeric-id":4591372,"id":"Q4591372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$3FBC8BE4-8D86-4115-9839-3EE0BCDD52F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93b02fc2f21dc972f518ce9d3a394dfa230b5ce4","datavalue":{"value":{"entity-type":"item","numeric-id":5091767,"id":"Q5091767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$27EA0A42-DF66-4343-9556-385D3B203331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc759260dc633ed9367d7c92a6857b926a5e36ab","datavalue":{"value":{"entity-type":"item","numeric-id":5212804,"id":"Q5212804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$7D0A88EF-9B82-4063-A33B-9126C5514DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be340d49fac87f8ffe1bcb06328c0744b66d038","datavalue":{"value":{"entity-type":"item","numeric-id":5875501,"id":"Q5875501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$86128758-940C-423F-9BA8-03AD41178C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a0c2c00c97298d6aa49dd4223f26b026b91b476","datavalue":{"value":{"entity-type":"item","numeric-id":5130845,"id":"Q5130845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$C8DF4D89-6738-4A3C-98CE-33F53D5A726F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"991b0516438ce8e159a63b121171e811d5805c46","datavalue":{"value":{"entity-type":"item","numeric-id":5092457,"id":"Q5092457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$4D64D1D5-110F-4F7D-86D5-0DC5102FB13B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5e8bffd2bfa80ebc8f71ab379f618c1227ff3f0","datavalue":{"value":{"entity-type":"item","numeric-id":5115702,"id":"Q5115702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5862347$0AF3324F-C779-4553-A17E-7513E83C7EEF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c00d31ecb103d4d8adeb371318027f5f40b1cbaa","datavalue":{"value":{"entity-type":"item","numeric-id":3007622,"id":"Q3007622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d969692fb26b118d0a168b614a068160048b461","datavalue":{"value":{"amount":"+0.9457219839096068","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":"Q5862347$5B0D88D8-B3C6-4D13-89A5-4A22FACBBA86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c49281188ca51c422c1bf370a73f8d38ce66e4c4","datavalue":{"value":{"entity-type":"item","numeric-id":2891385,"id":"Q2891385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed3c0ac08b857de1bec6dcea23c8c95a4d884547","datavalue":{"value":{"amount":"+0.9300662875175476","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":"Q5862347$2AA054BC-7E8A-499F-899B-097CCA664E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e389750a48bacc76ceb4bdd00209bc2f7fd3c4a","datavalue":{"value":{"entity-type":"item","numeric-id":5448802,"id":"Q5448802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77e1111866ece2a917d1e752196f47744361d2e7","datavalue":{"value":{"amount":"+0.8901866674423218","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":"Q5862347$B5B210C5-1B2C-4400-BA94-F33724440CAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db84dbd7d07f0106c02bb415bebbe948240f93a3","datavalue":{"value":{"entity-type":"item","numeric-id":5230302,"id":"Q5230302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3207b571f925de6e2cdffbb36d151c5335f59875","datavalue":{"value":{"amount":"+0.8405401706695557","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":"Q5862347$3C1D029A-0D03-4EBD-A6EC-F4588CF7B126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e67aa791dc10a94c067c3d99ff3516652fb97c2a","datavalue":{"value":{"entity-type":"item","numeric-id":3190691,"id":"Q3190691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"accb37f3e0c67ad1ab8e73748d437d59ee1dd03d","datavalue":{"value":{"amount":"+0.8270115256309509","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":"Q5862347$55F8315C-0F86-46BC-A77F-227E11C23C49","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5862347","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5862347"}}}}}