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

DOI10.1137/0220019MaRDI QIDQ3359132zbMATH OpenOpenAlexFDO

Authors Ron M. Roth, Gyora M. Benedek

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

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

Recommendations

• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• On some approximation problems concerning sparse polynomials over finite fields
• Randomized Interpolation and Approximation of Sparse Polynomials
• Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
• Publication:5748889

Cited in

(23)

• Randomized Interpolation and Approximation of Sparse Polynomials
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• The query complexity of finding local minima in the lattice
• An SVD analysis of equispaced polynomial interpolation
• Об аппроксимации булевых функций линейными разветвлениями;On approximations of Boolean functions by linear spreads
• -discrepancy sets and their application for interpolation of sparse polynomials
• Computing sparse GCD of multivariate polynomials via polynomial interpolation
• On learning multivariate polynomials under the uniform distribution
• DNF are teachable in the average case
• Interpolation of symmetric functions and a new type of combinatorial design
• SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials
• Learning sparse polynomial functions
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Learning sparse linear combinations of basis functions over a finite domain
• Efficiently Testing Sparse GF(2) Polynomials
• Almost optimal proper learning and testing polynomials
• On the zeros of Boolean polynomials
• Exact learning of linear combinations of monotone terms from function value queries
• Simple learning algorithms using divide and conquer
• On interpolating arithmetic read-once formulas with exponentiation
• Zero testing of \(p\)-adic and modular polynomials
• 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)$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3359132)