Abstract
What is the least surface area of a permutationsymmetric body B whose ℤⁿ translations tile ℝⁿ? Since any such body must have volume 1, the isoperimetric inequality implies that its surface area must be at least Ω(√n). Remarkably, Kindler et al. showed that for general bodies B this is tight, i.e. that there is a tiling body of ℝⁿ whose surface area is O(√n).
In theoretical computer science, the tiling problem is intimately related to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a "strong version" of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used in order to construct nontrivial tilings of ℝⁿ.
In this paper, motivated by the study of a symmetric parallel repetition, we consider the permutationsymmetric variant of the tiling problem in ℝⁿ. We show that any permutationsymmetric body that tiles ℝⁿ must have surface area at least Ω(n/√{log n}), and that this bound is tight, i.e. that there is a permutationsymmetric tiling body of ℝⁿ with surface area O(n/√{log n}). We also give matching bounds for the value of the symmetric parallel repetition of Raz’s odd cycle game.
Our result suggests that while strong parallel repetition fails in general, there may be important special cases where it still applies.
BibTeX  Entry
@InProceedings{braverman_et_al:LIPIcs.CCC.2021.5,
author = {Braverman, Mark and Minzer, Dor},
title = {{Optimal Tiling of the Euclidean Space Using PermutationSymmetric Bodies}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {5:15:48},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14279},
URN = {urn:nbn:de:0030drops142796},
doi = {10.4230/LIPIcs.CCC.2021.5},
annote = {Keywords: PCP, Parallel Repetition, Tilings}
}
Keywords: 

PCP, Parallel Repetition, Tilings 
Collection: 

36th Computational Complexity Conference (CCC 2021) 
Issue Date: 

2021 
Date of publication: 

08.07.2021 