A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length

We develop and analyze a new family of pseudorandom generators for polynomial threshold functions with respect to the Gaussian distribution. In particular, for any fixed degree we develop a generator whose seed length is subpolynomial in the error parameter, ε. We get particularly nice results for d...

Full description

Saved in:
Bibliographic Details
Main Author: Kane, Daniel M.
Format: Conference Proceeding
Language:English
Subjects:
Approximation methods
Gaussian distribution
Generators
Jacobian matrices
Polynomial threshold function
Polynomials
Pseudorandom generator
Random variables
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We develop and analyze a new family of pseudorandom generators for polynomial threshold functions with respect to the Gaussian distribution. In particular, for any fixed degree we develop a generator whose seed length is subpolynomial in the error parameter, ε. We get particularly nice results for degree 1 and degree 2 threshold functions, in which cases our seed length is O(log(n) + log 3/2 (1/ε)) and exp(O(log 2/3 (1/ε))), respectively.
ISSN:1093-0159
2575-8403
DOI:10.1109/CCC.2014.30