  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
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 $\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 \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.
