2026-08-05T11:37:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17668 2024-03-06T11:00:16Z ddc:004 open_access

Non-Adaptive Proper Learning Polynomials Bshouty, Nader H. Polynomial Learning Testing 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/ε)^{γ(s,ε)}log n queries where 2.66 ≤ γ(s,ε) ≤ 6.922 and runs in Õ(n)⋅ poly(s,1/ε) time. We also show that for any ε = 1/s^{O(1)} any non-adaptive learning algorithm must make at least (s/ε)^{Ω(1)}log n queries. Therefore, the query complexity of our algorithm is also polynomial in the optimal query complexity and optimal in n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nader H. Bshouty 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.16 urn:nbn:de:0030-drops-176689 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode