2026-07-23T05:17:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16583 2024-03-06T10:57:51Z ddc:004 open_access

Random Restrictions and PRGs for PTFs in Gaussian Space Kelley, Zander Meka, Raghu polynomial threshold function pseudorandom generator multivariate gaussian A polynomial threshold function (PTF) f: ℝⁿ → ℝ is a function of the form f(x) = sign(p(x)) where p is a polynomial of degree at most d. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address the question of designing pseudorandom generators (PRGs) for polynomial threshold functions (PTFs) in the gaussian space: design a PRG that takes a seed of few bits of randomness and outputs a n-dimensional vector whose distribution is indistinguishable from a standard multivariate gaussian by a degree d PTF. Our main result is a PRG that takes a seed of d^O(1) log(n/ε) log(1/ε)/ε² random bits with output that cannot be distinguished from an n-dimensional gaussian distribution with advantage better than ε by degree d PTFs. The best previous generator due to O'Donnell, Servedio, and Tan (STOC'20) had a quasi-polynomial dependence (i.e., seed length of d^O(log d)) in the degree d. Along the way we prove a few nearly-tight structural properties of restrictions of PTFs that may be of independent interest. Similar results were obtained in [Ryan O'Donnell et al., 2021] (independently and concurrently). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zander Kelley and Raghu Meka 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.21 urn:nbn:de:0030-drops-165836 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.21 eng https://creativecommons.org/licenses/by/4.0/legalcode