A local decision test for sparse polynomials

DOI10.1016/J.IPL.2010.07.012zbMATH Open1234.68461OpenAlexW2136567612MaRDI QIDQ407596FDOQ407596

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

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

zbMATH Keywords

randomized algorithmsmultivariate polynomialssparsity tests

Mathematics Subject Classification ID

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

Cites Work

• Randomized Interpolation and Approximation of Sparse Polynomials
• Property testing. A learning theory perspective
• Title not available (Why is that?)
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Sparse Polynomial Interpolation in Nonstandard Bases
• Interpolation of polynomials given by straight-line programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficiently Testing Sparse GF(2) Polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing juntas nearly optimally
• A new algorithm for the inversion of Hankel and Toeplitz matrices
• Testing juntas
• \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials

Cited In (7)

• Local tests for consistency of support hyperplane data.
• Arithmetic sketching
• Binomiality testing and computing sparse polynomials via witness sets
• Multiparty cardinality testing for threshold private intersection
• Multi-party threshold private set intersection with sublinear communication
• Linear independence, alternants, and applications
• Efficiently Testing Sparse GF(2) Polynomials

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)