We study bounds on the classical $*$-discrepancy and on its inverse.
Let $n^*_\infty(d,\e)$ be the inverse of the $*$-discrepancy, i.e.,
the minimal number of points
in dimension $d$ with the $*$-discrepancy at most $\e$.
We prove that $n^*_\infty(d,\e)$ depends
{\em linearly} on $d$ and at most quadratically on $\e^{-1}$.
We present three upper bounds on $n^*_\infty(d,\e)$, all of them are based on
probabilistic arguments and therefore they are non-constructive.
The linear in $d$ upper bound directly follows from
deep results of the theory of empirical processes but it contains
an unknown multiplicative factor.
Two other upper bounds are without unknown
factors but do not yield the linear (in $d$)
upper bound. One upper bound is based on an average case analysis
for the $L_p$-star discrepancy and our numerical results seem to
indicate
that it gives the best estimates for specific values of
$d$ and $\e$.
We also present two lower bounds on $n^*_\infty(d,\e)$.
For lower bounds, we allow
arbitrary coefficients in the discrepancy formula. We prove that
$n^*_\infty(d,\e)$ must be of order $d\,\log \e^{-1}$ and, roughly,
of order $d^{\lambda}\e^{-(1-\lambda)}$ for any $\lambda\in (0,1)$.
Acta Arithmetica, to appear.