A PRG for Gaussian Polynomial Threshold Functions

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II
Topic:A PRG for Gaussian Polynomial Threshold Functions
Speaker:Daniel Kane
Affiliation:Harvard University
Date:Tuesday, March 15
Time/Room:10:30am - 12:30pm/S-101

We define a polynomial threshold function to be a function of the form f(x) = sgn(p(x)) for p a polynomial. We discuss some recent techniques for dealing with polynomial threshold functions, particular when evaluated on random Gaussians. We show how to use these ideas to produce a pseudo random generator for degree-d polynomial threshold functions of Gaussians with seed length poly(2^d,log(n),epsilon^{-1}) .