An Invariance Principle for the Multi-slice, with Applications

Given an alphabet size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> thought of as a constant, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k⃗=(k₁, …, kₘ)</tex> whose entries sum of up <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> , the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k⃗</tex> -multi-slice is the set of vectors <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x∈[m]ⁿ</tex> in which each symbol <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i∈[m]</tex> appears precisely <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">kᵢ</tex> times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">[m]ⁿ, μⁿ</tex> ) in which <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">μ(i)=kᵢ/n</tex> . This answers a question raised by [21]. As applications of the invariance principle, we show: 1)An analogue of the “dictatorship test implies computational hardness” paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</tex> -ary CSP <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Pᵣ</tex> for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2r+12ʳ+o(1)</tex> satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$o(1)$</tex> . 2)A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3)In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</tex> called <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ζ</tex> -forests, which is a natural extension of the well-studied case of matchings.