2017/08/12 by Badih Ghazi, Ghazi, Badih, Pritish Kamath +3
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #cs.CC #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1708.03808
arxiv created 2017/08/12 · openalex publication_date 2017/08/12 · arxiv updated 2017/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℝ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 n0(δ) 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 n0(δ). 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 Xn and Yn respectively where \(Xi, Yi)\i=1n 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 n0(δ) 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 n0(δ).