Hypercontractivity on high dimensional expanders
Hypercontractivity on high dimensional expanders
复制标题
DOI：
10.1145/3519935.3520040
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Mitali Bafna;Max Hopkins;T. Kaufman;Shachar Lovett
中科院分区：
文献类型：
--
作者：
Mitali Bafna;Max Hopkins;T. Kaufman;Shachar Lovett
超收缩性是布尔函数分析中最强大的工具之一。最初是在离散超立方体上研究的，近年来人们对p偏立方体、切片或格拉斯曼等设置的扩展越来越感兴趣，其中超收缩性的变体已经发现了许多突破性的应用，包括Khot的2-2博弈猜想的解决方案（Khot，Minzer，Safra FOCS 2018）。在这项工作中，我们开发了一个新的理论hypercontractivity的高维扩展（HDX），一个重要的类的扩展复合物，最近看到了同样令人印象深刻的应用在编码理论和近似采样。我们的结果导致一个新的理解的结构上的布尔函数的HDX，包括一个紧密的类似的KKL定理和一个新的表征的非扩展集。与以前满足超压缩性的设置不同，HDX可以是不对称的，稀疏的，并且远离产品，这使得传统证明技术的应用具有挑战性。我们处理这些障碍，引入了两个新的工具的独立利益：一个新的显式组合傅立叶基础HDX的行为以及限制下，和一个新的本地到全球的方法分析更高的时刻。有趣的是，与同样适用于所有类型的扩展复合体的类似二阶矩方法不同，我们的工具本质上依赖于单纯结构。这表明了一个新的区分高维膨胀剂的基础上，他们的行为超过第二时刻。这是一个扩展的抽象。全文可在https://arxiv.org/abs/2111.09444上找到。
Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the p-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of Khot’s 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). In this work, we develop a new theory of hypercontractivity on high dimensional expanders (HDX), an important class of expanding complexes that has recently seen similarly impressive applications in both coding theory and approximate sampling. Our results lead to a new understanding of the structure of Boolean functions on HDX, including a tight analog of the KKL Theorem and a new characterization of non-expanding sets. Unlike previous settings satisfying hypercontractivity, HDX can be asymmetric, sparse, and very far from products, which makes the application of traditional proof techniques challenging. We handle these barriers with the introduction of two new tools of independent interest: a new explicit combinatorial Fourier basis for HDX that behaves well under restriction, and a new local-to-global method for analyzing higher moments. Interestingly, unlike analogous second moment methods that apply equally across all types of expanding complexes, our tools rely inherently on simplicial structure. This suggests a new distinction among high dimensional expanders based upon their behavior beyond the second moment. This is an extended abstract. The full paper may be found at https://arxiv.org/abs/2111.09444.