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

Details Hardness of discrepancy computation and epsilon-net verification in high dimension Hardness of discrepancy computation and epsilon-net verification in high dimension

2011-03-23

arxiv.org/abs/1103.4503v1

Computer Science

Computational Geometry

20 pages, 5 figures

Scientific paper

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}.

Affiliated with

Also associated with

No associations

Rating

Hardness of discrepancy computation and epsilon-net verification in high dimension does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness of discrepancy computation and epsilon-net verification in high dimension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness of discrepancy computation and epsilon-net verification in high dimension will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-441256