A local decision test for sparse polynomials

DOI10.1016/J.IPL.2010.07.012MaRDI QIDQ407596zbMATH OpenOpenAlexFDO

Authors Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld

Publication date 27 March 2012

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

Full work available at URL http://hdl.handle.net/1721.1/108433

zbMATH Keywords

multivariate polynomialsrandomized algorithmssparsity tests

Mathematics Subject Classification ID

Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• A new deterministic algorithm for sparse multivariate polynomial interpolation
• Sparse polynomial interpolation with finitely many values for the coefficients
• Efficiently Testing Sparse GF(2) Polynomials
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Sparse polynomial interpolation based on diversification

Cites work

• -discrepancy sets and their application for interpolation of sparse polynomials
• A new algorithm for the inversion of Hankel and Toeplitz matrices
• Efficiently Testing Sparse GF(2) Polynomials
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1241385 (Why is no real title available?)
• scientific article; zbMATH DE number 1254239 (Why is no real title available?)
• scientific article; zbMATH DE number 503193 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• Interpolation of polynomials given by straight-line programs
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Property testing. A learning theory perspective
• Randomized Interpolation and Approximation of Sparse Polynomials
• Sparse Polynomial Interpolation in Nonstandard Bases
• Testing juntas
• Testing juntas nearly optimally

Cited in

(12)

• Multiparty cardinality testing for threshold private intersection
• Multi-party threshold private set intersection with sublinear communication
• Binomiality testing and computing sparse polynomials via witness sets
• Randomness efficient testing of sparse black box identities of unbounded degree over the reals
• Efficiently Testing Sparse GF(2) Polynomials
• Arithmetic sketching
• Zero testing and equation solving for sparse polynomials on rectangular domains
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Linear independence, alternants, and applications
• Linear independence, alternants and applications
• On solving sparse polynomial factorization related problems
• Local tests for consistency of support hyperplane data.

This page was built for publication: A local decision test for sparse polynomials

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