论文标题
在高尺寸扩张器上的带束带的$ 2 $ 2 $ 2 $ - Query the当地测试的代码
On Good $2$-Query Locally Testable Codes from Sheaves on High Dimensional Expanders
论文作者
论文摘要
我们在本地可测试的代码（LTC）和高维扩张器之间公开了良好的$ 2 $ Query Query the Pross的联系。在这里，如果LTC具有恒定速率和线性距离，则称为好。我们对这项工作的重点是可测试的LTC，只有2美元的查询，这对理论计算机科学特别感兴趣。这是通过引入一个称为捆的新对象来完成的，该对象位于高维扩展器顶部。拓扑层面是拓扑的大量研究。在这里，我们介绍了简单络合物的滑轮。此外，我们定义了以前从未研究过的不断扩展的捆的概念。 我们提出一个框架，以利用这些高维膨胀器的盖子，从而使$ 2 $ Query LTC的良好无限家庭从高维扩展器上扩展。从高维扩展器和扩展的捆式开始开始，我们的框架生产了一个无限的代码系列，承认$ 2 $ Query-Query-Quester Tester。我们表明，如果最初的齐射高维扩张器满足某些条件，可以在恒定时间内检查一下，那么这些代码会形成一个良好的$ 2 $ - Query LTC的家族。 我们以迭代过程的形式为候选人提供了可以将其送入我们的框架的高维膨胀器的候选者，该过程猜测会产生高维扩张器和特殊的辅助纸条的候选者。 （由于计算局限性，我们无法直接验证这些候选人的框架的先决条件。）我们通过实验和启发式进行分析，并确定高维膨胀机的基本组的某些特性，这些属性足够（但没有必要）以获得所需的杂种，因此是一家不适的家族，并获得了一家良好的$ 2 $ 2 $ -Query LTC。
We expose a strong connection between good $2$-query locally testable codes (LTCs) and high dimensional expanders. Here, an LTC is called good if it has constant rate and linear distance. Our emphasis in this work is on LTCs testable with only $2$ queries, which are of particular interest to theoretical computer science. This is done by introducing a new object called a sheaf that is put on top of a high dimensional expander. Sheaves are vastly studied in topology. Here, we introduce sheaves on simplicial complexes. Moreover, we define a notion of an expanding sheaf that has not been studied before. We present a framework to get good infinite families of $2$-query LTCs from expanding sheaves on high dimensional expanders, utilizing towers of coverings of these high dimensional expanders. Starting with a high dimensional expander and an expanding sheaf, our framework produces an infinite family of codes admitting a $2$-query tester. We show that if the initial sheaved high dimensional expander satisfies some conditions, which can be checked in constant time, then these codes form a family of good $2$-query LTCs. We give candidates for sheaved high dimensional expanders which can be fed into our framework, in the form of an iterative process which conjecturally produces such candidates given a high dimensional expander and a special auxiliary sheaf. (We could not verify the prerequisites of our framework for these candidates directly because of computational limitations.) We analyse this process experimentally and heuristically, and identify some properties of the fundamental group of the high dimensional expander at hand which are sufficient (but not necessary) to get the desired sheaf, and consequently an infinite family of good $2$-query LTCs.
