Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension (Q413466)

The star discrepancy (or geometric discrepancy with respect to corners) of a set \(P\) of \(n\) points in the \(d\)-dimensional unit cube \([0,1]^d\) is the supremum, taken over all axis-parallel rectangles \(R = [0,x] \subseteq [0,1]^d\) (``corners''), absolute deviation of the number of points in \(R\) from the expected value \(n \lambda(R)\), where \(\lambda\) denotes the \(d\)-dimensional Lebesgue measure. It is well known that the star discrepancy of an \(n\)-point set can be computed in time \(n^{O(d)}\). Also, the decision problem if the star discrepancy exceeds a given value, is NP-hard if \(d\) is part of the input. This work presents a stronger lower bound by showing that the decision problem is even W[1]-hard with respect to \(d\). Consequently, algorithms with runtime bounded by \(f(d) n^{O(1)}\) do not exist unless FPT = W[1]. Analogous results are shown for the decision versions of a number of related problems: Computing the largest empty corner, the largest empty axis parallel rectangle, the red-blue discrepancy with respect to axis-parallel rectangles and several others. The first of these is even hard even to approximate within a factor of \(2^n\). Also, the problem of deciding whether a subset \(S\) of \(P\) is an \(\varepsilon\)-net with respect to half-spaces, is co-NP-hard and co-W[1]-hard.