Faster sparse multivariate polynomial interpolation of straight-line programs

DOI10.1016/j.jsc.2015.11.005zbMath1398.68693arXiv1412.4088OpenAlexW1941702124MaRDI QIDQ2635066

Andrew Arnold, Daniel S. Roche, Mark W. Giesbrecht

Publication date: 11 February 2016

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.4088

zbMATH Keywords

complexityrandomized algorithmsstraight-line programsparse interpolation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Numerical interpolation (65D05) Interpolation in approximation theory (41A05) Randomized algorithms (68W20)

Related Items (7)

Sparse polynomial interpolation based on derivatives ⋮ Learning algebraic decompositions using Prony structures ⋮ Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs ⋮ Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials ⋮ On the complexity of the Lickteig-Roy subresultant algorithm ⋮ Fast multivariate multi-point evaluation revisited ⋮ Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform

Cites Work

• Unnamed Item
• Unnamed Item
• Interpolating polynomials from their values
• Interpolation of polynomials given by straight-line programs
• Explaining the wheel sieve
• On fast multiplication of polynomials over arbitrary algebras
• Approximate formulas for some functions of prime numbers
• Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation
• Arithmetic Circuits: A survey of recent results and open questions
• Sparse interpolation over finite fields via low-order roots of unity
• Multivariate sparse interpolation using randomized Kronecker substitutions
• Powers of tensors and fast matrix multiplication
• Faster Integer Multiplication
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Learning Decision Trees Using the Fourier Spectrum
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Faster Sparse Interpolation of Straight-Line Programs
• Diversification improves interpolation
• Probability Inequalities for Sums of Bounded Random Variables
• Nearly optimal sparse fourier transform
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Symbolic-numeric sparse interpolation of multivariate polynomials
• Fast construction of irreducible polynomials over finite fields
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Faster sparse multivariate polynomial interpolation of straight-line programs