Computer Science/Discrete Mathematics Seminar I

Let K be a convex body in $R^n$. In some cases (say when K is a cube), we can tile $R^n$ using translates of K. However, in general (say when K is a ball) this is impossible. Nevertheless, we show that one can always cover space "smoothly" using translates of K, in the sense that *each* point in $R^n$ is covered by almost the same small number of translates of K (specifically, (1+-eps)poly(n)). Moreover, we show that this can be achieved by taking the translates to be the set of points in a random lattice. These results represent substantial improvements to bounds of Rogers from the 1950s. The key to the proof are recent breakthroughs due to Dvir, Dhar, and others regarding the discrete Kakeya problem. I will present some history, applications in engineering and computer science, and ideas of the proofs. No prerequisites beyond undergraduate material (measures, volumes, vector spaces over finite fields) will be assumed.

Based on joint work with Or Ordentlich and Barak Weiss (one paper published in J. AMS 2022 https://arxiv.org/abs/2006.00340 and another in progress)