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 R n into k parts, that maximizes the noise stability. An -optimal partition is one which is within additive of the optimal noise stability.

De, Mossel & Neeman (CCC 2017) raised the question of an explicit (computable) bound on the dimension n 0 ( ) in which we can find an -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 ( ) . (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 ) n i =1 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 -close to simulating Q , or does every non-interactive simulation protocol remain 2 -far from simulating Q ? The main underlying challenge here is to determine an explicit (computable) upper bound on the number of samples n 0 ( ) that can be drawn from P ( x y ) to get -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 0 1 , it remained open to answer the case where Q is a distribution over larger alphabet, say [ k ] [ k ] for 2"> k 2 . Recently De, Mossel & Neeman (in a follow-up work), address this challenge for all k 2 . In this work, we are able to recover this result as well, with improved explicit bounds on n 0 ( ) .