Computer Science/Discrete Mathematics Seminar II

A PRG for Gaussian Polynomial Threshold Functions

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}) .

Date & Time

March 15, 2011 | 10:30am – 12:30pm

Location

S-101

Speakers

Daniel Kane

Affiliation

Harvard University