Hi all,
Our next meeting in the Information Theory and Applications seminar will take place on Monday, May 20 at 10:00, in room A500.
I will speak about some recent advancements in the lattice covering problem.
See you there, Or (and Oron, Yuval and Alex)
---------------------------------------------
Title: Bounds on the density of smooth lattice coverings
Abstract: The epsilon-smooth covering density of a unit co-volume lattice L with respect to a convex body K is defined as the minimum volume of a dilate rK such that each point x\in R^n is rK-covered by (1\pm epsilon)Vol(r K) points in L. For any convex body K in R^n we show that for almost all lattices (with respect to the natural Haar-Siegel measure on the space of lattices) the epsilon-smooth covering density is polynomial in n. We also show similar results for random construction A lattices, provided that the ratio between the covering and packing radii of Z^n with respect to K is at most polynomial in n. Our proofs utilize a recent result of Dhar and Dvir on the discrete Kakeya problem. Joint work with Oded Regev and Barak Weiss