# Almost Optimal Proper Learning and Testing Polynomials

arXiv: https://arxiv.org/abs/2202.03207 · HTML: https://mlsanity.com/paper/2202.03207/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 29 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 1 of 1)

- [Almost Optimal Testers for Concise Representations](https://mlsanity.com/paper/1904.09958/) (2019)

## Abstract (arXiv)

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.