A local decision test for sparse polynomials

DOI10.1016/j.ipl.2010.07.012zbMath1234.68461OpenAlexW2136567612MaRDI QIDQ407596

Elena Grigorescu, Ronitt Rubinfeld, Kyomin Jung

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

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

Related Items

Arithmetic sketching, Multiparty cardinality testing for threshold private intersection, Multi-party threshold private set intersection with sublinear communication

Cites Work

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