Vi utvecklar och analyserar en ny familj av pseudorandom generatorer för polynom tröskelfunktioner med avseende på Gaussian distribution. I synnerhet, för varje fast grad vi utvecklar en generator vars utsädeslängd är subpolynomial i felparametern,. Vi får särskilt fina resultat för grad 1 och grad 2 tröskelfunktioner, i vilka fall vår utsädeslängd är O(log(n) + log 3/2 (1/ )) respektive exp(O (log 2/3 (1/ ) ).
För Gaussian distribution, REF gav en PRG som uppnår en sålängd av O(log n + log 3/2 (1/ε)
A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length
{'venue': '2014 IEEE 29th Conference on Computational Complexity (CCC)', 'journal': '2014 IEEE 29th Conference on Computational Complexity (CCC)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}