An Invariance Principle for the Multi-slice, with Applications
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer · 2022
Given an alphabet size$m\in\mathbb{N}$thought of as a constant, and$\vec{k}=(k_{1}, \ldots, k_{m})$whose entries sum of up$n$, the$\vec{k}$-multi-slice is the set of vectors$x\in[m]^{n}$in which each symbol$i\in[m]$appears precisely$k_{i}$times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ($[m]^{n}, \mu^{n}$) in which$\mu(i)=k_{i}/n$. 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$r$-ary CSP$\mathcal{P}_{r}$for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most$\frac{2r+1}{2^{r}}+o(1)$satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size$o(1)$. 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$H$called$\zeta$-forests, which is a natural extension of the well-studied case of matchings.