Dor Minzer

An invariance principle for the multi-slice, with applications

A multi-slice over an alphabet of size $m$ and dimension $n$ is a subset $S$ of all strings in $[m]^n$ with a prescribed number of coordinates equal to each one of the alphabet symbols. We prove an invariance principle for low-degree functions over $S$. Namely, we show that given a low-degree function $f$ on $S$, one may associate with it a low-degree function $g$ on $[m]^n$ such that the functions $f$ and $g$ “behave in a very similar manner”. As applications of our invariance principle, we prove analogs of classical results from Fourier analysis, as well as new hardness of approximation results assuming the Rich 2-to-1 Games Conjecture.

Talk recording on Youtube