max planck institut
informatik

# 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)
Title: The discrepancy of jittered sampling Benjamin Doerr Ecole Polytechnique, France Talk D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Wednesday, 3 August 2016 11:00 30 Minutes Saarbrücken E1 4 024
 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