FoCM 2014 conference
Workshop B5 - Information Based Complexity
December 16, 15:30 ~ 16:00 - Room B23
The weighted star discrepancy of Korobov's $p$-sets
Friedrich Pillichshammer
Johannes Kepler University Linz, Austria - friedrich.pillichshammer@jku.at
Tractability properties of various notions of discrepancy have been intensively studied in the last decade. In this presentation we consider the so-called weighted star discrepancy which was introduced by Sloan and Wo\'{z}niakowski in 1998. We give an overview of existence results and constructions of point sets which can achieve polynomial or even strong polynomial tractability for suitable choices of weights. Then, for prime numbers $p$, we consider Korobov's $p$-sets:
$P_{p,s}=\{\boldsymbol{x}_0,\ldots,\boldsymbol{x}_{p-1}\}$ with $$\boldsymbol{x}_n=\left(\left\{\frac{n}{p}\right\},\left\{\frac{n^2}{p}\right\},\ldots,\left\{\frac{n^s}{p}\right\}\right)\ \ \ \mbox{ for }\ n=0,1,\ldots,p-1,$$
$Q_{p^2,s}=\{\boldsymbol{x}_0,\ldots,\boldsymbol{x}_{p^2-1}\}$ with $$\boldsymbol{x}_n=\left(\left\{\frac{n}{p^2}\right\},\left\{\frac{n^2}{p^2}\right\},\ldots,\left\{\frac{n^s}{p^2}\right\}\right)\ \ \ \mbox{ for }\ n=0,1,\ldots,p^2-1,$$
and $R_{p^2,s}=\{\boldsymbol{x}_{a,k}\ : \ a,k \in \{0,\ldots,p-1\}\}$ with $$\boldsymbol{x}_{a,k}=\left(\left\{\frac{k}{p}\right\},\left\{\frac{a k}{p}\right\},\ldots,\left\{\frac{a^{s-1} k}{p}\right\}\right)\ \ \ \mbox{ for }\ a,k=0,1,\ldots,p-1,$$
and prove bounds on their weighted star discrepancy which hold for any choice of weights. For product weights we give conditions under which the discrepancy bounds are independent of the dimension $s$. This implies strong polynomial tractability for the weighted star discrepancy. We also show that a very weak condition on the product weights suffices to achieve polynomial tractability.
Joint work with Josef Dick (UNSW Sydney, Australia).