2026-07-25T06:06:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8861 2024-03-06T10:42:53Z ddc:004 open_access

Dimension Reduction for Polynomials over Gaussian Space and Applications Ghazi, Badih Kamath, Pritish Raghavendra, Prasad Dimension reduction Low-degree Polynomials Noise Stability Non-Interactive Simulation 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 an application, we obtain an explicit upper bound on the dimension of an epsilon-optimal noise-stable Gaussian partition. In fact, we address the more general problem of upper bounding the number of samples needed to epsilon-approximate any joint distribution that can be non-interactively simulated from a correlated Gaussian source. Our results significantly improve (from Ackermann-like to "merely" exponential) the upper bounds recently proved on the above problems by De, Mossel & Neeman [CCC 2017, SODA 2018 resp.] and imply decidability of the larger alphabet case of the gap non-interactive simulation problem posed by Ghazi, Kamath & Sudan [FOCS 2016]. Our technique of dimension reduction for low-degree polynomials is simple and can be seen as a generalization of the Johnson-Lindenstrauss lemma and could be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Badih Ghazi and Pritish Kamath and Prasad Raghavendra 2018 Is Part Of LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2018.28 urn:nbn:de:0030-drops-88616 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.28 eng https://creativecommons.org/licenses/by/3.0/legalcode