Dimension Reduction for Polynomials over Gaussian Space and Applications

DOI10.4230/LIPICS.CCC.2018.28MaRDI QIDQ5121916zbMATH OpenFDO

Authors Badih Ghazi, Pritish Kamath, Prasad Raghavendra

Publication date 22 September 2020

Full work available at URL https://arxiv.org/abs/1708.03808

zbMATH Keywords

dimension reductionlow-degree polynomialsnoise stabilitynon-interactive simulation

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: 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 $mathbb{R}^n$ into $k$ parts, that maximizes the noise stability. An $delta$-optimal partition is one which is within additive $delta$ of the optimal noise stability. De, Mossel & Neeman (CCC 2017) raised the question of proving a computable bound on the dimension $n_0(delta)$ in which we can find an $delta$-optimal partition. While De et al. provide such a bound, using our new technique, we obtain improved explicit bounds on the dimension $n_0(delta)$. 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,1imes0,1$, Ghazi, Kamath and Sudan (FOCS 2016) proved a computable bound on the number of samples $n_0(delta)$ that can be drawn from $P(x,y)$ to get $delta$-close to $Q$ (if it is possible at all). Recently De, Mossel & Neeman obtained such bounds when $Q$ is a distribution over $[k]imes[k]$ for any $kge2$. We recover this result with improved explicit bounds on $n_0(delta)$.

Recommendations

• scientific article; zbMATH DE number 7140483
• Noise stability is computable and approximately low-dimensional
• A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions

Cites work

• A counterexample to strong parallel repetition
• A Parallel Repetition Theorem
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Common randomness and secret key generation with a helper
• Common randomness in information theory and cryptography. I. Secret sharing
• Common randomness in information theory and cryptography. II. CR capacity
• Communication complexity of permutation-invariant functions
• Efficient deterministic approximate counting for low-degree polynomial threshold functions
• Entangled games are hard to approximate
• Extensions of Lipschitz mappings into a Hilbert space
• Gaussian bounds for noise correlation of functions
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• scientific article; zbMATH DE number 3497786 (Why is no real title available?)
• scientific article; zbMATH DE number 1394316 (Why is no real title available?)
• scientific article; zbMATH DE number 3019401 (Why is no real title available?)
• Hypercontractivity of simple random variables
• Impossibility of local state transformation via hypercontractivity
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Information Equals Amortized Communication
• Information value of two-prover games
• Maximally stable Gaussian partitions with discrete applications
• Noise stability is computable and approximately low-dimensional
• Non interactive simulation of correlated distributions is decidable
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• On Extracting Common Random Bits From Correlated Sources
• On measures of dependence
• On Non-Interactive Simulation of Joint Distributions
• On Sequences of Pairs of Dependent Random Variables
• On the role of shared randomness in simultaneous communication
• On the Shannon capacity of a graph
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Parallel repetition in projection games and a concentration bound
• Parallel repetition: simplification and the no-signaling case
• Private vs. common random bits in communication complexity
• Resource-efficient common randomness and secret-key schemes
• Secret key agreement by public discussion from common information
• Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
• Standard simplices and pluralities are not the most noise stable
• The common information of two dependent random variables
• The Shannon capacity of a graph and the independence numbers of its powers
• Tripartite Entanglement Transformations and Tensor Rank

Cited in

(10)

• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• Secure non-interactive simulation: feasibility and rate
• scientific article; zbMATH DE number 5177320 (Why is no real title available?)
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Noise stability is computable and approximately low-dimensional
• Three candidate plurality is stablest for small correlations
• Secure non-interactive simulation from arbitrary joint distributions
• The computational advantage of MIP* vanishes in the presence of noise
• The computational advantage of MIP* vanishes in the presence of noise
• Decidability of fully quantum nonlocal games with noisy maximally entangled states

This page was built for publication: Dimension Reduction for Polynomials over Gaussian Space and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121916)