Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$

DOI10.1137/0220019zbMath0733.41003OpenAlexW2124394334MaRDI QIDQ3359132

Gyora M. Benedek, Ron M. Roth

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/25eca1ae04b3a0fbcd2113913dcf72d911a0cda3

zbMATH Keywords

algorithmprobabilistic polynomial-time algorithmt-sparse function

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Interpolation in approximation theory (41A05) Approximation by polynomials (41A10) Decoding (94B35) Discrete mathematics in relation to computer science (68R99)

Related Items (12)

On learning multivariate polynomials under the uniform distribution ⋮ Simple learning algorithms using divide and conquer ⋮ Exact learning of linear combinations of monotone terms from function value queries ⋮ Learning sparse linear combinations of basis functions over a finite domain ⋮ Almost optimal proper learning and testing polynomials ⋮ Unnamed Item ⋮ Efficiently testing sparse \(\text{GF}(2)\) polynomials ⋮ DNF are teachable in the average case ⋮ On interpolating arithmetic read-once formulas with exponentiation ⋮ Zero testing of \(p\)-adic and modular polynomials ⋮ The query complexity of finding local minima in the lattice ⋮ The complexity of sparse polynomial interpolation over finite fields

This page was built for publication: Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$