Abstract: The unit cube tiles R^d by Z^d, in the sense that its translations by vectors from Z^d cover R^d. It is natural to ask what is the minimal surface area of a body that tiles R^d by Z^d. The volume of any such body should clearly be at least 1, and therefore its surface area must be at least that of a unit volume ball, which of order sqrt(d). The surface area of the cube, however, is of order d, and no better tiling was known. In this work we use a random construction to show that the optimal surface area is indeed of order sqrt(d), namely there exist bodies that tile R^d as a cube would, but have sphere-like surface areas.

Tiling problems were considered for well over a century, but this particular tiling problem was also recently considered in computer science because of its relations with the Unique Games conjecture and with the Parallel Repetition problem. Indeed, our current result follows from the same idea that was used recently by Raz in his counter example for the strong Parallel Repetition conjecture.

Joint work with Ryan O'Donnell, Anup Rao, and Avi Wigderson