Abstract: Consider the following question: what is the least surface area of a unit volume body that tiles the d-dimensional space under translations by ${\mathbb Z}^d$? The answer is at most $2d$ as the cube tiles ${\mathbb R}^d$ and at least $\sqrt{2\pi e}\cdot \sqrt{d}$ since amongst all unit volume bodies the sphere has the least surface area. Surprisingly, the answer to this question is $O(\sqrt{d})$, in other words, there is a body that is like the cube, in that it tiles ${\mathbb R}^d$ and yet closer to the sphere with respect to surface area. More surprisingly, the construction of this body was inspired by questions in the theory of computational complexity related to hardness amplification, in particular, in attempts to prove Khot's "unique games conjecture". In this talk, I'll sketch this construction, explaining the connection to the unique games conjecture and parallel repetition theorem. No prior knowledge of computation complexity will be assumed.
Ref: G. Kindler, A. Rao, Ryan O'Donnell, A. Wigderson Spherical Cubes: Optimal Foams from Computational Hardness Amplification Communications of the ACM, vol. 55, no. 10, pp. 90-97, 2012.
http://dx.doi.org/10.1145/2347736.2347757
