Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

摘要

Low-degree polynomial approximations to the sign function underlie pseudorandom generators for halfspaces, as well as algorithms for agnostically learning halfspaces. We study the limits of these constructions by proving inapproximability results for the