Kelley, Zander ;
Meka, Raghu
Random Restrictions and PRGs for PTFs in Gaussian Space
Abstract
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 wellstudied 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 ndimensional 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 ndimensional 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 quasipolynomial dependence (i.e., seed length of d^O(log d)) in the degree d. Along the way we prove a few nearlytight 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).
BibTeX  Entry
@InProceedings{kelley_et_al:LIPIcs.CCC.2022.21,
author = {Kelley, Zander and Meka, Raghu},
title = {{Random Restrictions and PRGs for PTFs in Gaussian Space}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {21:121:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16583},
URN = {urn:nbn:de:0030drops165836},
doi = {10.4230/LIPIcs.CCC.2022.21},
annote = {Keywords: polynomial threshold function, pseudorandom generator, multivariate gaussian}
}
11.07.2022
Keywords: 

polynomial threshold function, pseudorandom generator, multivariate gaussian 
Seminar: 

37th Computational Complexity Conference (CCC 2022)

Issue date: 

2022 
Date of publication: 

11.07.2022 