Dimension Reduction for Polynomials over Gaussian Space and Applications
share
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, analogous to the Johnson-Lindenstrauss lemma. As applications, we address the following problems: 1. Computability of Approximately Optimal Noise Stable function over Gaussian space: The goal 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 proving a computable bound on the dimension n_0(δ) in which we can find an δ-optimal partition. While De et al. provide such a bound, using our new technique, we obtain improved explicit bounds on the dimension n_0(δ). 2. Decidability of 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 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. In the special where Q is a joint distribution over {0,1}×{0,1}, Ghazi, Kamath and Sudan (FOCS 2016) proved a computable bound on the number of samples n_0(δ) that can be drawn from P(x,y) to get δ-close to Q (if it is possible at all). Recently De, Mossel & Neeman obtained such bounds when Q is a distribution over [k] × [k] for any k > 2. We recover this result with improved explicit bounds on n_0(δ).
READ FULL TEXT