In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:
(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:
The goal here is to find a partition of $\mathbb{R}^n$ into $k$ parts, that maximizes the noise stability. An $\varepsilon$-optimal partition is one which is within additive $\varepsilon$ of the optimal noise stability.
De, Mossel & Neeman (CCC 2017) raised the question of an explicit (computable) bound on the dimension $n_0(\varepsilon)$ in which we can find an $\varepsilon$-optimal partition.
De et al. already provide such an explicit bound. Using our dimension reduction technique, we are able to obtain improved explicit bounds on the dimension $n_0(\varepsilon)$.
(II) Decidability of Approximate Non-Interactive Simulation of Joint Distributions:
A "non-interactive simulation" problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where $\{(X_i, Y_i)\}_{i=1}^n$ are drawn i.i.d. from $P(x,y)$ can generate pairs $U$ and $V$ respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to $Q(u,v)$. Even when $P$ and $Q$ are extremely simple, it is open in several cases if $P$ can simulate $Q$.
Ghazi, Kamath & Sudan (FOCS 2016) formulated a gap problem of deciding whether there exists a non-interactive simulation protocol that comes $\varepsilon$-close to simulating $Q$, or does every non-interactive simulation protocol remain $2\varepsilon$-far from simulating $Q$? The main underlying challenge here is to determine an explicit (computable) upper bound on the number of samples $n_0(\varepsilon)$ that can be drawn from $P(x,y)$ to get $\varepsilon$-close to $Q$ (if it were possible at all).
While Ghazi et al. answered the challenge in the special case where $Q$ is a joint distribution over $\{0,1\} \times \{0,1\}$, it remained open to answer the case where $Q$ is a distribution over larger alphabet, say $[k] \times [k]$ for $k > 2$. Recently De, Mossel & Neeman (in a follow-up work), address this challenge for all $k \ge 2$. In this work, we are able to recover this result as well, with improved explicit bounds on $n_0(\varepsilon)$.
---
Our technique of dimension reduction for low-degree polynomials is simple and analogous to the Johnson-Lindenstrauss lemma, and could be of independent interest.
