{"entities":{"Q1382408":{"pageid":1393148,"ns":120,"title":"Item:Q1382408","lastrevid":68766504,"modified":"2026-04-13T01:55:21Z","type":"item","id":"Q1382408","labels":{"en":{"language":"en","value":"Efficient construction of a small hitting set for combinatorial rectangles in high dimension"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1134662"}},"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":"Q1382408$323B8927-633B-4461-AF90-4C0521C6D9FF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ce4cfa96a723b8087233cd305269ca4c1d670a3","datavalue":{"value":{"text":"Efficient construction of a small hitting set for combinatorial rectangles in high dimension","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382408$65EBFAA7-D29C-4A58-A943-BA51C4034191","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"00f891d75c42435fc242879a2e219774c4d2e0e7","datavalue":{"value":"0886.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$7DD50B5A-D822-4E9B-BDCD-7CF472126F3E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d85aef6e084bda4ccff6fad1f541cf541597c28","datavalue":{"value":"10.1007/BF01200907","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$D07D8517-F483-4A6A-9961-2ED8B18ACE18","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$D9400705-DF95-4196-B0AE-D264139C4006","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"12641de0c7a44a9d60a6f8d503a212499c146538","datavalue":{"value":{"time":"+1998-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382408$0982D623-A29C-4147-B05E-166A582A88D9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8cd881d2bb5845e84f28584d645080f7c36ddef4","datavalue":{"value":"A rectangle is a subset of \\([m]^d=\\{1,2,3,\\dots,m\\}^d\\) of form \\(R_1\\times R_2\\times \\dots\\times R_d\\). Its volume is \\((\\Pi |R_i|)/m^d\\). A deterministic algorithm is given which, on input integers \\(d\\), \\(m\\) and a real number \\(\\varepsilon\\in (0,1)\\) produces a subset of \\([m]^d\\) that hits every rectangle of volume at least \\(\\varepsilon\\). The time is a polynomial in \\(md/\\varepsilon\\) and the size of the subset is a polynomial in \\(m(\\log d)/\\varepsilon\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382408$9037DAF6-F79D-4FFC-92BD-B0684D5097D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$915DD234-0414-46A4-80BD-4842BB54050B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$4E9F9716-66E5-440F-944E-8FD5DC935687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$1B040353-4FCE-46C2-AC83-048E39FE157A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$056A4A61-F813-45C5-A714-73CDCE9274AE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"faa9d06e717bf55a87638542fa818a74ae0a480f","datavalue":{"value":"1134662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$769D6D23-04D2-4878-94C3-DD3201588E95","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d84e515400a627a4fe5987f549f810ec779002d","datavalue":{"value":"small hitting set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382408$9AA41209-7355-4DC3-BF51-4EF2B3EA4D26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3d96e3d74138447af545d0cb2d3866006bca24c","datavalue":{"value":"rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382408$4ABAE7F1-9F16-4261-8BB3-1EA41B4EC8FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81ab3c92f44f395b025a7c9836ac25b0a0d1756","datavalue":{"value":{"entity-type":"item","numeric-id":178480,"id":"Q178480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$3AD87147-392D-4D1F-B393-C001D1ABF7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d5a2f70848f5f6284f8ed2480b6f2c9e1c6ebac","datavalue":{"value":{"entity-type":"item","numeric-id":685335,"id":"Q685335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$72B4B74C-7D59-4D8C-AE6F-11A658056C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f09421b6aff8e8d7720ab7e9d35f10a9deb5a2","datavalue":{"value":{"entity-type":"item","numeric-id":1112076,"id":"Q1112076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$357277F9-EA8D-4DE5-92CA-E767DB344CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11e9247244d7c5a83ff00535a80d8b3489fb0336","datavalue":{"value":{"entity-type":"item","numeric-id":294713,"id":"Q294713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$93966082-7955-41B0-A2C5-7535D82A0C5B","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":"Q1382408$742CEDE2-6B81-41A1-99F3-6148ACF029F7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c847610ade77b047e3075d35766cbb1d381ec23","datavalue":{"value":{"entity-type":"item","numeric-id":1259907,"id":"Q1259907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$B20BA5FC-EF0F-4AF3-9DCB-41C991F9628F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1e5777a42bc3c08aa95b622cdd8e9d79bef8a26","datavalue":{"value":{"entity-type":"item","numeric-id":1120201,"id":"Q1120201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$683655CB-3CAE-48C7-9E91-DA169612D48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c3fb0ef3c7cbeb1b19e8a3632e3bd5fcfcda10","datavalue":{"value":{"entity-type":"item","numeric-id":1165257,"id":"Q1165257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$280C7ADB-5093-4530-849C-C91908C479A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd7c217abccafcadc4755ff6c8107a9aae3039f3","datavalue":{"value":{"entity-type":"item","numeric-id":1375692,"id":"Q1375692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$8B3C1B0D-6851-4DB1-8692-6E560F5EF5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2cf5a2575092d69512381ce3ca2190a160efcc8","datavalue":{"value":{"entity-type":"item","numeric-id":4033769,"id":"Q4033769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$7872A3C4-0652-4C6C-B97D-552E010CD769","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":"Q1382408$DCF8ADC8-B92C-4D4F-BC5A-A87D17A12E19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"093fc8397e936eec865082c631fc83e3421354ab","datavalue":{"value":{"entity-type":"item","numeric-id":3495640,"id":"Q3495640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$42E3F45E-B8B0-4F78-A8A4-8D83A3EFE4E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a27c18c71bc11e347397a6fd2eac2fb9bb4ef2ee","datavalue":{"value":{"entity-type":"item","numeric-id":1107314,"id":"Q1107314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$592EF1F7-014C-4C35-9B4B-076C0A290BC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9da857881651568f3a237665ef58e62d5927e2bc","datavalue":{"value":{"entity-type":"item","numeric-id":1923854,"id":"Q1923854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382408$AD1C2DB9-8242-480F-A84F-2B50E604B021","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"005912b47e2d4177660b9edada4ffe709c3e4beb","datavalue":{"value":"https://doi.org/10.1007/bf01200907","type":"string"},"datatype":"url"},"type":"statement","id":"Q1382408$A4EAC722-D67C-40AE-893F-664EF49DB052","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef54dc03eab86ecf5afc0c674eb6258012946c32","datavalue":{"value":"W2611007065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382408$5C65F5A4-0B7F-47E2-8D99-CFD95E1A79B5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08936376fd3851c56b5b4c278fb3e590b2bb268e","datavalue":{"value":{"entity-type":"item","numeric-id":1007576,"id":"Q1007576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2aec0f573594a6f3a8d4627ef88b945ec942f0a","datavalue":{"value":{"amount":"+0.8677210807800293","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":"Q1382408$7592FAB5-7ADB-4E22-AF31-C75DE2723111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5897c327413491b54f08a4e770f9549fd286424","datavalue":{"value":{"entity-type":"item","numeric-id":4501678,"id":"Q4501678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61e5c52687d89a7a18861b15a697d1644834aa3f","datavalue":{"value":{"amount":"+0.8168980479240417","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":"Q1382408$C863B2C3-E8E6-42B1-A693-17B064B0AAC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23fbd612fac2a8c6b0d4d28518315bf417e202e2","datavalue":{"value":{"entity-type":"item","numeric-id":5048940,"id":"Q5048940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd28fc832dbd1ab71eb254c5a04036f722491813","datavalue":{"value":{"amount":"+0.7670338153839111","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":"Q1382408$57D29DF3-2456-462E-83E1-46C82F557F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08ee25fa6a9d040206059952669f17f4d34356bc","datavalue":{"value":{"entity-type":"item","numeric-id":3167414,"id":"Q3167414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"525b877b4686368e2adb830518e27309f42dccf9","datavalue":{"value":{"amount":"+0.7598633170127869","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":"Q1382408$2C0A19DE-C657-4E2C-98F1-544280BC88BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient construction of a small hitting set for combinatorial rectangles in high dimension","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_construction_of_a_small_hitting_set_for_combinatorial_rectangles_in_high_dimension"}}}}}