Agreement Testing Theorems on Layered Set Systems
Agreement Testing Theorems on Layered Set Systems
复制标题
分层集系统上的一致性检验定理
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Irit Dinur
中科院分区：
文献类型：
--
作者：
Yotam Dikstein;Irit Dinur
我们引入了分层子集的框架，并给出了一个集合系统支持一致性测试的充分条件。一致性测试是一种特定类型的性质测试，它推广了如平面与平面测试等PCP测试。先前的工作表明高维扩展对于一致性测试是有用的。我们将这些结果扩展到更一般的子集族，超越了单纯复形。这些包括：
- 对于集合为高维扩展器的面的集合系统的一致性测试。我们的新测试适用于复形的所有维度，无论是双侧扩展的情况还是单侧分块扩展的情况。这改进并扩展了Dinur和Kaufman（2017年FOCS）的早期工作，并适用于拟阵，以及可能许多其他的复形。
- 对于集合为高维扩展器中顶点的邻域的集合系统的一致性测试。这个族类似于在PCP定理的间隙放大证明中使用的扩展器邻域族。这个集合系统非常自然，但并不位于单纯复形中，并且展示了我们证明技术的一些通用性。
- 对子空间族（也称为格拉斯曼偏序集）的一致性测试。这将经典的低次一致性测试扩展到低次多项式的设定之外。我们的分析依赖于在单纯复形上的一种新的随机游走，我们称之为“补随机游走”，它可能具有独立的研究价值。这种随机游走将图上的非懒惰随机游走推广到更高维度，并且比先前研究的单纯复形上的随机游走具有明显更好的扩展性。
We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test. Previous work has shown that high dimensional expansion is useful for agreement tests. We extend these results to more general families of subsets, beyond simplicial complexes. These include – Agreement tests for set systems whose sets are faces of high dimensional expanders. Our new tests apply to all dimensions of complexes both in case of two-sided expansion and in the case of one-sided partite expansion. This improves and extends an earlier work of Dinur and Kaufman (FOCS 2017) and applies to matroids, and potentially many additional complexes. – Agreement tests for set systems whose sets are neighborhoods of vertices in a high dimensional expander. This family resembles the expander neighborhood family used in the gap-amplification proof of the PCP theorem. This set system is quite natural yet does not sit in a simplicial complex, and demonstrates some versatility in our proof technique. – Agreement tests on families of subspaces (also known as the Grassmann poset). This extends the classical low degree agreement tests beyond the setting of low degree polynomials. Our analysis relies on a new random walk on simplicial complexes which we call the “complement random walk” and which may be of independent interest. This random walk generalizes the non-lazy random walk on a graph to higher dimensions, and has significantly better expansion than previously-studied random walks on simplicial complexes.
DOI：
10.1109/focs.2019.00021
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Alev, Vedat Levi;Granha Jeronimo, Fernando;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur