Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-098 | 12th July 2022 13:34

Non-Adaptive Proper Learning Polynomials

RSS-Feed




TR22-098
Authors: Nader Bshouty
Publication: 13th July 2022 05:55
Downloads: 164
Keywords: 


Abstract:

We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive learning algorithm must make at least $(s/\epsilon)^{\Omega(1)}\log n$ queries. Therefore, the query complexity of our algorithm is also polynomial in the optimal query complexity and optimal in $n$.



ISSN 1433-8092 | Imprint