On learning multivariate polynomials under the uniform distribution

DOI10.1016/S0020-0190(97)00021-5zbMath1337.68143MaRDI QIDQ290214

Nader H. Bshouty

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

finite fieldsmultivariate polynomialsPAC-learningmembership queries

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

Almost optimal proper learning and testing polynomials ⋮ Unnamed Item ⋮ Efficiently testing sparse \(\text{GF}(2)\) polynomials

Cites Work

• Interpolating polynomials from their values
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Learning Boolean functions in an infinite attribute space
• Queries and concept learning
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Randomized Interpolation and Approximation of Sparse Polynomials

This page was built for publication: On learning multivariate polynomials under the uniform distribution