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.
翻译:Boolean 函数分析中最有力的工具之一,超链性是超立方体。在对离散超立方体进行初始研究后,近些年来,人们越来越关注扩展诸如美元偏差的立方体、切片或格拉斯曼尼安等环境,超立方体的变体发现了一些突破性应用,包括解决Khot 2-2游戏的预测(Khot, Minzer, Safra FOCS 2018) 。在这项工作中,我们开发了一种高维扩张器超立性的新理论(HDX ), 高维扩张器(HDX ) 是一个重要的复杂复杂的复杂复杂复杂结构, 最近,在编码理论理论和近似抽样取样中都出现了类似令人瞩目的应用。 我们的成果导致对Boolean 功能在HDX 上的结构有了新的理解, 包括KKLTHT的近似相似相似的模拟模拟, 以及所有非展变的系统。 与以往的环境不同,HX 可能是不对称的, 使得基于传统证据技术的第二层的新的工具具有挑战性。我们处理这些障碍, 在两种新的二种新工具中, 我们处理这些障碍与两种独立的应用中, 一种明确的四级分析方法在现代的高度的高度的压低压压压压下, 。