Computer Science/Discrete Mathematics Seminar I

We say a body B tiles the space R^n if the shifted bodies (B+z), for z\in Z^n, are all disjoint and cover R^n. In this talk, we consider the problem of finding the least surface area a tiling body B can have, for bodies B symmetric under coordinate permutation. This problem arises naturally in the study of parallel repetition theorems, which are an important component in many hardness of approximation results. For general bodies, the isoperimeric inequality implies that any tiling body B must have surface area at least \sqrt{n}, and somewhat surprisingly this bound is asymptotically tight. With the symmetry requirement, the trivial upper bound is O(n) for the unit cube, and the trivial lower bound is still \sqrt{n}. In this talk we show that the answer for the symmetric case is \Theta(n/\sqrt{\log n}). We will discuss connections to the parallel repetition theorem. Specifically, while the strong parallel repetition conjecture was refuted by Raz in 2008, our result suggests that there might be important special cases where it still applies. Joint work with Dor Minzer