  Discrepancy measures how uniformly distributed a point set is with respect to
a given set of ranges. There are two notions of discrepancy, namely continuous
discrepancy and combinatorial discrepancy. Depending on the ranges, several
possible variants arise, for example star discrepancy, box discrepancy, and
discrepancy of half-spaces. In this paper, we investigate the hardness of these
problems with respect to the dimension d of the underlying space.
  All these problems are solvable in time {n^O(d)}, but such a time dependency
quickly becomes intractable for high-dimensional data. Thus it is interesting
to ask whether the dependency on d can be moderated.
  We answer this question negatively by proving that the canonical decision
problems are W[1]-hard with respect to the dimension. This is done via a
parameterized reduction from the Clique problem. As the parameter stays linear
in the input parameter, the results moreover imply that these problems require
{n^\Omega(d)} time, unless 3-Sat can be solved in {2^o(n)} time.
  Further, we derive that testing whether a given set is an {\epsilon}-net with
respect to half-spaces takes {n^\Omega(d)} time under the same assumption. As
intermediate results, we discover the W[1]-hardness of other well known
problems, such as determining the largest empty star inside the unit cube. For
this, we show that it is even hard to approximate within a factor of {2^n}.
