Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

Mark Bun, Thomas Steinke

Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorith…