TY - GEN
T1 - Optimal tiling of the euclidean space using permutation-symmetric bodies
AU - Braverman, Mark
AU - Minzer, Dor
N1 - Publisher Copyright:
© Mark Braverman and Dor Minzer; licensed under Creative Commons License CC-BY 4.0
PY - 2021/7/1
Y1 - 2021/7/1
N2 - What is the least surface area of a permutation-symmetric body B whose Zn translations tile Rn? 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 Rn 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 non-trivial tilings of Rn. In this paper, motivated by the study of a symmetric parallel repetition, we consider the permutation-symmetric variant of the tiling problem in Rn. We show that any permutation-symmetric body that tiles Rn must have surface area at least Ω(n/√log n), and that this bound is tight, i.e. that there is a permutation-symmetric tiling body of Rn 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.
AB - What is the least surface area of a permutation-symmetric body B whose Zn translations tile Rn? 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 Rn 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 non-trivial tilings of Rn. In this paper, motivated by the study of a symmetric parallel repetition, we consider the permutation-symmetric variant of the tiling problem in Rn. We show that any permutation-symmetric body that tiles Rn must have surface area at least Ω(n/√log n), and that this bound is tight, i.e. that there is a permutation-symmetric tiling body of Rn 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.
KW - PCP
KW - Parallel repetition
KW - Tilings
UR - http://www.scopus.com/inward/record.url?scp=85115312441&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115312441&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2021.5
DO - 10.4230/LIPIcs.CCC.2021.5
M3 - Conference contribution
AN - SCOPUS:85115312441
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th Computational Complexity Conference, CCC 2021
A2 - Kabanets, Valentine
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th Computational Complexity Conference, CCC 2021
Y2 - 20 July 2021 through 23 July 2021
ER -