Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The discrepancy of jittered sampling
Speaker:Benjamin Doerr
coming from:Ecole Polytechnique, France
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Wednesday, 3 August 2016
Duration:30 Minutes
Building:E1 4
The geometric discrepancy problem asks for sets of N points evenly distributed in the d-dimensional unit cube [0,1)^d. Here "evenly distributed" means that ideally each axis-parallel rectangles R anchored in 0 contains $N \volume(R)$ points. It is not totally obvious that for this problem methods and thinking from discrete algorithmics are useful, but in a few recent works we were successfully following this road. For example, in 2013 we showed that a random point set usually leads to a rectangle R having $\sqrt{dN}$ points too many or too few, which provided a matching lower bound to the upper bounds of Heinrich et al. (2001) and Aistleitner (2011). In this work, we regard point set constructed from partitioning the unit cube into small cubes and putting exactly one point randomly into each cube. Again by using elementary combinatorial arguments, we determine the discrepancy of such point sets. Our result improves the recent upper and lower bounds of Steinerberger and Pausinger (2016) and disproves their guess on the true order of magnitude.
Name(s):Benjamin Doerr
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Benjamin Doerr, 08/01/2016 10:57 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Benjamin Doerr, 08/01/2016 11:02 PM
  • Benjamin Doerr, 08/01/2016 10:57 PM -- Created document.