Almost Optimal Proper Learning and Testing Polynomials

Nader H. Bshouty

We give the first almost optimal polynomial-time proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. For $s$-sparse polynomial over…