{"entities":{"Q413466":{"pageid":415233,"ns":120,"title":"Item:Q413466","lastrevid":61668447,"modified":"2026-04-11T00:51:33Z","type":"item","id":"Q413466","labels":{"en":{"language":"en","value":"Hardness of discrepancy computation and \\(\\varepsilon\\)-net verification in high dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6031124"}},"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":"Q413466$6DF33C7F-B0BC-43E1-9938-F68BA5E40DF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"543a678a9a52d2114b11b59a0d96d3225a24e369","datavalue":{"value":{"text":"Hardness of discrepancy computation and \\(\\varepsilon\\)-net verification in high dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q413466$62CC0A34-9230-4FB6-81E8-F48B068511B4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ff0103488d4831c65abdbd6cb9aa573c4819e170","datavalue":{"value":"1273.11116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q413466$FFE6F29E-0DFC-451C-B69A-73ABF26EDA6C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"76ae8fac84c8474007f890a5d740b8004a7cda91","datavalue":{"value":{"entity-type":"item","numeric-id":262253,"id":"Q262253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$58FAEB47-A304-4988-A474-40765C5961E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c31e34753d6d88354136116eb637796e7d9ee9ae","datavalue":{"value":{"entity-type":"item","numeric-id":359744,"id":"Q359744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$28F1F2AC-74D5-4687-9A1E-54B129DFF60A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11324fa342c81c30ac095bea5b5286aa7a4bc5ff","datavalue":{"value":{"entity-type":"item","numeric-id":309798,"id":"Q309798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$24AFD649-11FD-4D18-A1A8-81D54CDF726B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7570ab45dd29a22db8efde87fc308e3f8b7080be","datavalue":{"value":{"entity-type":"item","numeric-id":359745,"id":"Q359745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$2F69CA89-9541-4E53-9888-20F963EAECF5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$D97E71DD-7E73-49B2-BF31-7C85F235B293","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7a1c120dc379e55cc80f89048abc2e9af9a7f71","datavalue":{"value":{"time":"+2012-05-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":"Q413466$67553DA5-382C-4E1B-8BB7-EEACEF8B86F7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d503c2183e475a61583573b55fab6564130a2db5","datavalue":{"value":{"entity-type":"item","numeric-id":211679,"id":"Q211679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$12F3A738-B55B-4B9E-8CA5-53BC549EE275","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"086c0286ca441f85b3f6a04f4cff158d1709cb93","datavalue":{"value":"11K38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q413466$40F82A1F-0123-4C49-8F9F-28ECF01F549C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q413466$A2AB86DE-AB5D-4070-8313-0635D013BE15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9ee0bf715019f88099ecc8f26499d3edb0208fa","datavalue":{"value":"6031124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q413466$C9B2AFCC-E87B-4A16-ADA9-E9567D5C6145","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f30f01baa0dbe102ed14d61f6acd511c378aa58","datavalue":{"value":"discrepancy","type":"string"},"datatype":"string"},"type":"statement","id":"Q413466$5CB52C7D-244C-4815-8DAB-1F7E2784F7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e181728ddf46ff122e8ac5f1321a3c7dc22d331e","datavalue":{"value":"epsilon-nets","type":"string"},"datatype":"string"},"type":"statement","id":"Q413466$0F096526-55C9-4D78-8658-B0AC7F6D048D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"156587c6ed28353969b0e0f2acd62881e75662ac","datavalue":{"value":"geometric dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q413466$0E5C02EB-24CC-414C-A312-3C5B6945011F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q413466$0BCCB5AC-D2A6-4150-8728-C0D4572DF1BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q413466$41CA4944-2E51-45F1-BCE3-4138538C7AC9","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":"Q413466$C11E82F4-D205-466D-A3C8-556E778EF3C9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"56f81f18c64025ca3ac775999d098a3aaa8f21bb","datavalue":{"value":"https://doi.org/10.1016/j.jco.2011.09.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q413466$5EDD6592-82EB-42BB-929B-6123B7E28A26","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2bc26590d56a2b0fcac8fd60038738ac60df6b70","datavalue":{"value":"W1508410079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q413466$F040DD8E-3C3B-4B05-8126-C2DECC737677","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a3186065719fc0dc6ecff1124cf6028376f25e9","datavalue":{"value":{"entity-type":"item","numeric-id":3631896,"id":"Q3631896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$A5EC5758-BFD3-4F4E-89E4-B58D33DBC83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94c6f2a7eada9c07f889a73e48235fee5316772e","datavalue":{"value":{"entity-type":"item","numeric-id":3557005,"id":"Q3557005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$5A03E9A7-DBDC-4D9A-B8C6-52808FAFD1F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46b1f833df9ad261e45ba32ee4f5ee7dba50ac4f","datavalue":{"value":{"entity-type":"item","numeric-id":3189027,"id":"Q3189027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$0606AE50-C1E2-41AD-909F-049657BC900B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a537736f9b22dce3438f63f3b326244b3898d1","datavalue":{"value":{"entity-type":"item","numeric-id":3579411,"id":"Q3579411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$F97F7F0B-62C7-4FFD-B72E-7435547A3A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5db62294eafad9cf203905acbd394ce8cd05cafd","datavalue":{"value":{"entity-type":"item","numeric-id":290268,"id":"Q290268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$9DEE9C8B-85C3-44ED-B1E1-8D3DABC23654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1de42504ce667266ce591b8331d2abd083a0c4f","datavalue":{"value":{"entity-type":"item","numeric-id":4515159,"id":"Q4515159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$DB119DC9-77C5-41C9-9E45-E06B05720E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"551d1d56aa539f7df8b218f6d9eec877ef98d2a9","datavalue":{"value":{"entity-type":"item","numeric-id":2568440,"id":"Q2568440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$94462DE7-71D5-40D2-A637-50018454DA2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69ae1356392a9ee908070b676add6712b407926d","datavalue":{"value":{"entity-type":"item","numeric-id":708312,"id":"Q708312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$BD334AB5-C7A9-47FE-AFF9-2C0EFE9E00DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$E613B86A-5391-4416-A159-AB1B4B37B04B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a628d6c050af191e3b9c0d662c552e3c35cf8b7a","datavalue":{"value":{"entity-type":"item","numeric-id":678412,"id":"Q678412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$C119435B-05AE-4D6F-9CB8-AE7E4B4B0E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fde5fe6d6cf004b974f195bb9134bf1f2f2be7c","datavalue":{"value":{"entity-type":"item","numeric-id":1950392,"id":"Q1950392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$E2800C07-F42D-40C2-8A25-6D0190A50E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6958abb9a66cf8eaff7d6fca55e02aa9da43bec","datavalue":{"value":{"entity-type":"item","numeric-id":1856362,"id":"Q1856362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$CA49F9C5-FB2F-4AB9-9B72-82506B609BAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$9CFC9D66-8A71-4DD6-BA9B-D79ACAB640B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6041a1341b13024c64aeedaf65bfe7efab8e85f9","datavalue":{"value":{"entity-type":"item","numeric-id":2483204,"id":"Q2483204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$768F963E-4CB0-426C-BCA9-C2F950FBFD01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18ab06ac372d8e4baee00da73dbe418e8395e019","datavalue":{"value":{"entity-type":"item","numeric-id":1023397,"id":"Q1023397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$C96770A5-2A48-4E4B-B234-14D8BE661AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d50f8d7f7fb78d13d9136abf1be65711198cfd6","datavalue":{"value":{"entity-type":"item","numeric-id":1089803,"id":"Q1089803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$88BE11F2-995B-44DF-B87B-F36282147E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f2430422484b4f3e06deef91af47df4dbae6361","datavalue":{"value":{"entity-type":"item","numeric-id":5906395,"id":"Q5906395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$DE586E8C-BCEE-4BE1-A7B7-7B41FE4561FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$9FF6C8D1-4C78-4107-A462-598B441D9D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"027df8bdf8699e71b027b511f354ddc26e7905d3","datavalue":{"value":{"entity-type":"item","numeric-id":4003879,"id":"Q4003879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$B8E68C61-1003-4E8A-BD4B-A4B0EFF9EC24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8980a603e8f55b2deb86c15ebf2efed72fc08829","datavalue":{"value":{"entity-type":"item","numeric-id":5404461,"id":"Q5404461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$08515A87-1953-4CF3-AA9A-B404E39C0DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$89FA7D4F-DAFC-489C-9118-7C0B9B93F795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"198084a8fed73278fe45695b9f134a4a527e0639","datavalue":{"value":{"entity-type":"item","numeric-id":1347864,"id":"Q1347864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$2A62AA33-A3DC-4801-B4AF-20CCEF92EF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q413466$9F0445D0-090D-4570-B811-7BB7CCD6F237","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ada1c8e80f75cb24fcf62036f0b3d59f9cab5675","datavalue":{"value":"10.1016/J.JCO.2011.09.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q413466$DB993A6A-C663-4C4C-8A99-FB4E4B6E7C07","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4e70574c1825b5747b8daa7e1f96ab4c64ce91e","datavalue":{"value":{"entity-type":"item","numeric-id":5419106,"id":"Q5419106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cb9461855e57d536bd82fda883e26063ce9ef7d","datavalue":{"value":{"amount":"+0.8313821","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":"Q413466$B382B34F-DA46-423D-8A2F-2E7A90D767AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2a04b114704359586c6cdb19b2d6d6c8431edcc","datavalue":{"value":{"entity-type":"item","numeric-id":4907581,"id":"Q4907581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83d7d594a4ae2de01d9bacd8d6c79d36b1ba5f9f","datavalue":{"value":{"amount":"+0.8313819","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":"Q413466$AC687DFC-25C0-4B14-B74B-2374DD7657F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29f1a1ccf4c1bfe4b8fbb79bcc8627df209f2b95","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"530d7a3c323fed961be0f3bdaa21bd0b3cf078b8","datavalue":{"value":{"amount":"+0.8304397","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":"Q413466$4B212D21-A92D-41EB-9F04-303D14759E80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3936286d3ab4afc3c073ddb65d0b205b470af38","datavalue":{"value":{"entity-type":"item","numeric-id":1611071,"id":"Q1611071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c819263972333c4f2aba59759f2eb9a20953d7c","datavalue":{"value":{"amount":"+0.829268","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":"Q413466$6B0F9515-CAE9-4E73-A4AF-10A2A507B25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9d66a49db47721cbb58925376e9ed351684c883","datavalue":{"value":{"entity-type":"item","numeric-id":5365142,"id":"Q5365142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01205c9b70e22030e5fc46c87b8e901d3eef5a24","datavalue":{"value":{"amount":"+0.82908726","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":"Q413466$E01E5926-D9B1-4373-8981-AED29060F6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ec4c506adfc83eda1b4350e59b773caf31b69ef","datavalue":{"value":{"entity-type":"item","numeric-id":2947585,"id":"Q2947585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91db844121145ae1386464419aed35316d8ab54d","datavalue":{"value":{"amount":"+0.82440966","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":"Q413466$2EDB7B47-D715-4A35-A11A-963EC64177EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c899233a97341adbd3970c0c68666e874ff0002a","datavalue":{"value":{"entity-type":"item","numeric-id":1316651,"id":"Q1316651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e691e7b05d8ee8a33f14f1586d3acb6455acb541","datavalue":{"value":{"amount":"+0.8240154","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":"Q413466$F73CE129-64D6-4FA4-88FA-85560278A080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4b52e35e1d345b9b32967cacd2084e30cb7129c","datavalue":{"value":{"entity-type":"item","numeric-id":1402543,"id":"Q1402543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e8bde68272d54286715cb158e2983f968f32a30","datavalue":{"value":{"amount":"+0.8233764","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":"Q413466$BD5BBE8D-F428-413A-9048-F11FE1AF3172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f870f4823b18fe99b40cfa065f5969261db9c2be","datavalue":{"value":{"entity-type":"item","numeric-id":6065226,"id":"Q6065226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"518f5b517f7d392af23ffd56658a5a6d1f12cf4a","datavalue":{"value":{"amount":"+0.8170355","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":"Q413466$F1F1BA9F-BDA7-431D-B02D-7EAE643683E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9110e11304fcca1a58ff47bc642b4702759ed4f3","datavalue":{"value":{"entity-type":"item","numeric-id":5874541,"id":"Q5874541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49ae6e41b4c9cd94333b369331f215a2f6cd9b2c","datavalue":{"value":{"amount":"+0.81211996","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":"Q413466$B8774F2E-3214-41ED-B54E-00BD4D94BA78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dfac7fca11e000608ba10b0b3a9fdcf283844136","datavalue":{"value":"The star discrepancy (or geometric discrepancy with respect to corners) of a set \\(P\\) of \\(n\\) points in the \\(d\\)-dimensional unit cube \\([0,1]^d\\) is the supremum, taken over all axis-parallel rectangles \\(R = [0,x] \\subseteq [0,1]^d\\) (``corners''), absolute deviation of the number of points in \\(R\\) from the expected value \\(n \\lambda(R)\\), where \\(\\lambda\\) denotes the \\(d\\)-dimensional Lebesgue measure. It is well known that the star discrepancy of an \\(n\\)-point set can be computed in time \\(n^{O(d)}\\). Also, the decision problem if the star discrepancy exceeds a given value, is NP-hard if \\(d\\) is part of the input.NEWLINENEWLINEThis work presents a stronger lower bound by showing that the decision problem is even W[1]-hard with respect to \\(d\\). Consequently, algorithms with runtime bounded by \\(f(d) n^{O(1)}\\) do not exist unless FPT = W[1].NEWLINENEWLINEAnalogous results are shown for the decision versions of a number of related problems: Computing the largest empty corner, the largest empty axis parallel rectangle, the red-blue discrepancy with respect to axis-parallel rectangles and several others. The first of these is even hard even to approximate within a factor of \\(2^n\\). Also, the problem of deciding whether a subset \\(S\\) of \\(P\\) is an \\(\\varepsilon\\)-net with respect to half-spaces, is co-NP-hard and co-W[1]-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q413466$02EC9E60-7941-4EC2-9FBA-347EEA087E82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hardness of discrepancy computation and \\(\\varepsilon\\)-net verification in high dimension","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hardness_of_discrepancy_computation_and_%5C(%5Cvarepsilon%5C)-net_verification_in_high_dimension"}}}}}