论文标题
使用对称体的欧几里得空间的最佳瓷砖
Optimal tiling of the Euclidean space using symmetric bodies
论文作者
论文摘要
对称体$ b $的最小表面积是什么，其$ \ mathbb {z}^n $ translations tile $ \ mathbb {r}^n $？由于任何此类机构都必须具有$ 1 $的体积，因此等等不等式意味着其表面积必须至少为$ω（\ sqrt {n}）$。值得注意的是，Kindler等人表明，对于一般物体$ b $，这是紧密的，即\ \ \ the有$ \ mathbb {r}^n $的瓷砖主体，其表面积为$ O（\ sqrt {n}）$。 在理论计算机科学中，平铺问题与平行重复定理（PCPS中的重要组成部分）密切相关，更具体地说是在平行重复定理的“强版本”是否具有的问题中。拉兹（Raz）使用奇怪的循环游戏表明，强有力的并行重复一般失败了，随后使用这些想法来构建$ \ mathbb {r}^n $的非平凡斜利。 在本文中，由对对称并行重复的研究激励，我们考虑了$ \ Mathbb {r}^n $中平地问题的对称变体。我们表明，任何瓷砖$ \ mathbb {r}^n $的对称体必须具有至少$ω（n/\ sqrt {\ log n}）$，并且该绑定是紧密的，即，在$ \ m mathbb {r}^n $ a corperiance $ o（n/s）中，有一个对称的瓷砖范围的对称范围的范围。我们还为Raz奇数周期游戏的对称并行重复的价值提供了匹配界限。 我们的结果表明，尽管强有力的平行重复总体上失败了，但仍有重要的特殊情况仍然适用。
What is the least surface area of a symmetric body $B$ whose $\mathbb{Z}^n$ translations tile $\mathbb{R}^n$? Since any such body must have volume $1$, the isoperimetric inequality implies that its surface area must be at least $Ω(\sqrt{n})$. Remarkably, Kindler et al.\ showed that for general bodies $B$ this is tight, i.e.\ that there is a tiling body of $\mathbb{R}^n$ whose surface area is $O(\sqrt{n})$. In theoretical computer science, the tiling problem is intimately 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 $\mathbb{R}^n$. In this paper, motivated by the study of a symmetric parallel repetition, we consider the symmetric variant of the tiling problem in $\mathbb{R}^n$. We show that any symmetric body that tiles $\mathbb{R}^n$ must have surface area at least $Ω(n/\sqrt{\log n})$, and that this bound is tight, i.e.\ that there is a symmetric tiling body of $\mathbb{R}^n$ with surface area $O(n/\sqrt{\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.
