Hardness of discrepancy computation and ε-net verification in high dimension

Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. Depending on the ranges, several variants arise, including star discrepancy, box discrepancy, and discrepancy of halfspaces. These problems are solvable in time nO(d), where d is the dimension of the underlying space. As such a dependency on d becomes intractable for high-dimensional data, we ask whether it can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension, implying that no f(d)⋅nO(1)-time algorithm is possible for any function f(d) unless FPT=W[1]. We also discover the W[1]-hardness of other well known problems, such as determining the largest empty box that contains the origin and is inside the unit cube. This is shown to be hard even to approximate within a factor of 2n.

► We study the complexity of discrepancy computation with respect to the dimension. ► We show that computing the star and box discrepancy of a point set is W[1]-hard. ► We show that computing the red-blue discrepancy of a point set is NP- and W[1]-hard. ► We show that computing the maximum empty anchored box is W[1]-hard.