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

2012/10/04 by Kane, Daniel M. · 1 citation
#60G15 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Probability (math.PR)

paper · doi:10.48550/arxiv.1210.1280

Abstract

We develop a pseudorandom generator that fools degree-d polynomial threshold functions in n variables with respect to the Gaussian distribution and has seed length O_c,d(log(n) ε^-c).

Cited by

• PTF Testing Lower Bounds for Non-Gaussian Component Analysis

Related

• A Small PRG for Polynomial Threshold Functions of Gaussians
• A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
• Pseudorandom Generators for Polynomial Threshold Functions
• A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian\n Setting
• Random restrictions and PRGs for PTFs in Gaussian Space