Almost Optimal Proper Learning and Testing Polynomials

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 n variables and ε=1/sβ, β>1, our algorithm makes qU=left(fracsεright)^fraclog ββ+O(frac1β)+ tilde Oleft(sright)left(logfrac1εright)log n queries. Notice that our query complexity is sublinear in 1/ε and almost linear in s. All previous algorithms have query complexity at least quadratic in s and linear in 1/ε. We then prove the almost tight lower bound qL=left(fracsεright)^fraclog ββ+Omega(frac1β)+ Omegaleft(sright)left(logfrac1εright)log n, Applying the reduction in~citeBshouty19b with the above algorithm, we give the first almost optimal polynomial-time tester for s-sparse polynomial. Our tester, for β>3.404, makes tilde Oleft(fracsεright) queries.