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