k-Independent Gaussians Fool Polynomial Threshold Functions

2010/12/07 by Kane, Daniel M. · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1012.1614

Abstract

We show that any O_d(ε^{-4d 7d})-independent family of Gaussians ε-fools any degree-d polynomial threshold function.

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 Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length
• A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions
• A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
• Bounded Independence Fools Degree-2 Threshold Functions