{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:43:26Z","timestamp":1776797006739,"version":"3.51.2"},"reference-count":14,"publisher":"American Mathematical Society (AMS)","issue":"287","license":[{"start":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T00:00:00Z","timestamp":1410307200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n By a profound result of Heinrich, Novak, Wasilkowski, and Wo\u017aniakowski the inverse of the star-discrepancy\n \n \n \n \n \n n<\/mml:mi>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msup>\n (<\/mml:mo>\n s<\/mml:mi>\n ,<\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n n^*(s,\\varepsilon )<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n satisfies the upper bound\n \n \n \n \n \n n<\/mml:mi>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msup>\n (<\/mml:mo>\n s<\/mml:mi>\n ,<\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n )<\/mml:mo>\n \n \u2264\n \n <\/mml:mo>\n \n c<\/mml:mi>\n \n \n a<\/mml:mi>\n b<\/mml:mi>\n s<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msub>\n s<\/mml:mi>\n \n \n \u03b5\n \n <\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n n^*(s,\\varepsilon ) \\leq c_{\\mathrm {abs}} s \\varepsilon ^{-2}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This is equivalent to the fact that for any\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n s<\/mml:mi>\n s<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n there exists a set of\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n points in\n \n \n \n \n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n \n ]<\/mml:mo>\n s<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n [0,1]^s<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n whose star-discrepancy is bounded by\n \n \n \n \n \n c<\/mml:mi>\n \n \n a<\/mml:mi>\n b<\/mml:mi>\n s<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msub>\n \n s<\/mml:mi>\n \n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n N<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n c_{\\mathrm {abs}} s^{1\/2} N^{-1\/2}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The proof is based on the observation that a random point set satisfies the desired discrepancy bound with positive probability. In the present paper we prove an applied version of this result, making it applicable for computational purposes: for any given number\n \n \n \n \n q<\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n q \\in (0,1)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n there exists an (explicitly stated) number\n \n \n \n \n c<\/mml:mi>\n (<\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n c(q)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n such that the star-discrepancy of a random set of\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n points in\n \n \n \n \n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n \n ]<\/mml:mo>\n s<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n [0,1]^s<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is bounded by\n \n \n \n \n c<\/mml:mi>\n (<\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n \n s<\/mml:mi>\n \n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n N<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n c(q) s^{1\/2} N^{-1\/2}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with probability at least\n \n \n \n q<\/mml:mi>\n q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , uniformly in\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n s<\/mml:mi>\n s<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-2013-02773-1","type":"journal-article","created":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T03:04:33Z","timestamp":1378868673000},"page":"1373-1381","source":"Crossref","is-referenced-by-count":17,"title":["Probabilistic discrepancy bound for Monte Carlo point sets"],"prefix":"10.1090","volume":"83","author":[{"given":"Christoph","family":"Aistleitner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Hofer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2013,9,10]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/j.jco.2011.03.001","article-title":"Covering numbers, dyadic chaining and discrepancy","volume":"27","author":"Aistleitner, Christoph","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1515\/MCMA.2008.007","article-title":"Component-by-component construction of low-discrepancy point sets of small size","volume":"14","author":"Doerr, Benjamin","year":"2008","journal-title":"Monte Carlo Methods Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0929-9629","issn-type":"print"},{"issue":"5","key":"3","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/j.jco.2010.03.004","article-title":"Algorithmic construction of low-discrepancy point sets via dependent randomized rounding","volume":"26","author":"Doerr, Benjamin","year":"2010","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.jco.2011.09.001","article-title":"Hardness of discrepancy computation and \ud835\udf00-net verification in high dimension","volume":"28","author":"Giannopoulos, Panos","year":"2012","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jco.2007.08.003","article-title":"Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy","volume":"24","author":"Gnewuch, Michael","year":"2008","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"Research Paper 95, 20","DOI":"10.37236\/819","article-title":"Construction of minimal bracketing covers for rectangles","volume":"15","author":"Gnewuch, Michael","year":"2008","journal-title":"Electron. J. Combin."},{"key":"7","doi-asserted-by":"crossref","unstructured":"M. Gnewuch. Entropy, randomization, derandomization, and discrepancy. In Monte Carlo and quasi-Monte Carlo methods 2010. Springer Proceedings in Mathematics and Statistics, Vol. 23, L. Plaskota; H. Wo\u017aniakowski (Eds.), Springer, p. 43 \u2013 78, 2012.","DOI":"10.1007\/978-3-642-27440-4_3"},{"issue":"2","key":"8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jco.2008.10.001","article-title":"Finding optimal volume subintervals with \ud835\udc58-points and calculating the star discrepancy are NP-hard problems","volume":"25","author":"Gnewuch, Michael","year":"2009","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/S0885-064X(03)00014-1","article-title":"Some open problems concerning the star-discrepancy","volume":"19","author":"Heinrich, Stefan","year":"2003","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.4064\/aa96-3-7","article-title":"The inverse of the star-discrepancy depends linearly on the dimension","volume":"96","author":"Heinrich, Stefan","year":"2001","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1016\/j.jco.2004.01.001","article-title":"Covering numbers, Vapnik-\u010cervonenkis classes and bounds for the star-discrepancy","volume":"20","author":"Hinrichs, Aicke","year":"2004","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"12","unstructured":"A. Hinrichs. Discrepancy, Integration and Tractability. Preprint. Available at \\url{http:\/\/users.minet.uni-jena.de\/ hinrichs\/paper\/50\/article.pdf}."},{"key":"13","series-title":"EMS Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4171\/026","volume-title":"Tractability of multivariate problems. Vol. 1: Linear information","volume":"6","author":"Novak, Erich","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037190265"},{"key":"14","series-title":"EMS Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4171\/084","volume-title":"Tractability of multivariate problems. Volume II: Standard information for functionals","volume":"12","author":"Novak, Erich","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037190845"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02773-1\/S0025-5718-2013-02773-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02773-1\/S0025-5718-2013-02773-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:53:51Z","timestamp":1776794031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02773-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,10]]},"references-count":14,"journal-issue":{"issue":"287","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["S0025-5718-2013-02773-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2013-02773-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9,10]]}}}