Testably Learning Polynomial Threshold Functions

We show that PTFs of arbitrary constant degree can be testably learned up to excess errorε > 0 in time npoly(1/ε). This qualitatively matches the best known guarantees in the agnostic model. Our results build on a connection between testable learning andfooling.