An Invariance Principle for the Multi-slice, with Applications

arXiv2110.10725MaRDI QIDQ6380876FDOQ6380876

Authors: Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer 

Publication date: 20 October 2021

Abstract: Given an alphabet size $minmathbbN$ thought of as a constant, and $veck=(k_1,ldots,k_m)$ whose entries sum of up $n$, the $veck$-multi-slice is the set of vectors $xin[m{]}^n$ in which each symbol $iin[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,m{u}^n)$ in which $mu(i)=k_i/n$. This answers a question raised by Filmus et al. 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 $frac2r+12^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 cite{MosselGaussian} 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.

This page was built for publication: An Invariance Principle for the Multi-slice, with Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380876)