AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The star discrepancy of a set of points is an important discrepancy measure, in among other things numerical integration, but unfortunately all known algorithms for computing or bounding it (e.g., approximating it) scale very badly with the dimension -- for n points in d dimensions, the best results both for computing it and for giving a constant-factor approximation have a running time like n^(d/2). (In some applications, the dimension can range in the hundreds, so this is clearly problematic.)

In this talk, I give a quick review of some methods that have been proposed for the problem, and give evidence from parameterized complexity that computing the exact discrepancy with a significantly better running time (in particular, a better dependency on d) is unlikely (i.e., W[1]-hard).

Joint work with Panos Giannopoulos, Christian Knauer,
and Daniel Werner.

Magnus Wahlström

--email hidden

passcode not visible

logged in users only