Interpolation of polynomials given by straight-line programs

DOI10.1016/j.tcs.2009.03.030zbMath1172.68064OpenAlexW2100899126MaRDI QIDQ1029336

Sanchit Garg, Éric Schost

Publication date: 10 July 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.030

zbMATH Keywords

interpolationstraight-line program

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Related Items (12)

Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Sparse polynomial interpolation based on derivatives ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Learning algebraic decompositions using Prony structures ⋮ Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs ⋮ A local decision test for sparse polynomials ⋮ On the evaluation of some sparse polynomials ⋮ Detecting lacunary perfect powers and computing their roots ⋮ A fast parallel sparse polynomial GCD algorithm ⋮ Sparse polynomials in FLINT ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interpolation of shifted-lacunary polynomials
• \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
• Interpolating polynomials from their values
• On fast multiplication of polynomials over arbitrary algebras
• Lower bounds for diophantine approximations
• Straight-line programs in geometric elimination theory
• Early termination in sparse interpolation algorithms
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• Newton-Hensel interpolation lifting
• Change of order for regular chains in positive dimension
• Computing Rational Zeros of Integral Polynomials by p-Adic Expansion
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Greatest common divisors of polynomials given by straight-line programs
• Randomized Interpolation and Approximation of Sparse Polynomials
• EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS
• Symbolic-numeric sparse interpolation of multivariate polynomials

This page was built for publication: Interpolation of polynomials given by straight-line programs