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.
