Polynomial Interpolation from Multiples

Joachim Von Zur Gathen; Igor E. Shparlinski

Polynomial Interpolation from Multiples

Joachim Von Zur Gathen^*, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

6 Citations (Scopus)

Abstract

We are given an unknown polynomial f ∈ Z[x] by a black box which on input a ℤ returns a value r_a · f(a) for some unknown nonzero rational numbers r_a. If we have appropriate upper bounds on the numerator and denominator of r_a and the degree of f, then the coefficients of f can be computed in probabilistic polynomial time.

Original language	English
Title of host publication	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Ian Munro
Place of Publication	New York
Publisher	Society for Industrial and Applied Mathematics Publications
Pages	1125-1130
Number of pages	6
ISBN (Print)	089871558X
Publication status	Published - 2004
Event	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: 11 Jan 2004 → 13 Jan 2004

Other

Other	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans, LA.
Period	11/01/04 → 13/01/04

Keywords

Approximate computation
Black box polynomial
Hidden polynomial
Integer lattices
Short vectors

Cite this

@inproceedings{662c9055f56a4be594355f0434791ca1,

title = "Polynomial Interpolation from Multiples",

abstract = "We are given an unknown polynomial f ∈ Z[x] by a black box which on input a ℤ returns a value ra · f(a) for some unknown nonzero rational numbers ra. If we have appropriate upper bounds on the numerator and denominator of ra and the degree of f, then the coefficients of f can be computed in probabilistic polynomial time.",

keywords = "Approximate computation, Black box polynomial, Hidden polynomial, Integer lattices, Short vectors",

author = "{Von Zur Gathen}, Joachim and Shparlinski, {Igor E.}",

year = "2004",

language = "English",

isbn = "089871558X",

pages = "1125--1130",

editor = "Ian Munro",

booktitle = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics Publications",

address = "United States",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

Von Zur Gathen, J & Shparlinski, IE 2004, Polynomial Interpolation from Multiples. in I Munro (ed.), Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics Publications, New York, pp. 1125-1130, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States, 11/01/04.

Polynomial Interpolation from Multiples. / Von Zur Gathen, Joachim; Shparlinski, Igor E.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Ian Munro. New York: Society for Industrial and Applied Mathematics Publications, 2004. p. 1125-1130.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Polynomial Interpolation from Multiples

AU - Von Zur Gathen, Joachim

AU - Shparlinski, Igor E.

PY - 2004

Y1 - 2004

N2 - We are given an unknown polynomial f ∈ Z[x] by a black box which on input a ℤ returns a value ra · f(a) for some unknown nonzero rational numbers ra. If we have appropriate upper bounds on the numerator and denominator of ra and the degree of f, then the coefficients of f can be computed in probabilistic polynomial time.

AB - We are given an unknown polynomial f ∈ Z[x] by a black box which on input a ℤ returns a value ra · f(a) for some unknown nonzero rational numbers ra. If we have appropriate upper bounds on the numerator and denominator of ra and the degree of f, then the coefficients of f can be computed in probabilistic polynomial time.

KW - Approximate computation

KW - Black box polynomial

KW - Hidden polynomial

KW - Integer lattices

KW - Short vectors

UR - http://www.scopus.com/inward/record.url?scp=1842591228&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:1842591228

SN - 089871558X

SP - 1125

EP - 1130

BT - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Munro, Ian

PB - Society for Industrial and Applied Mathematics Publications

CY - New York

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

Polynomial Interpolation from Multiples

Abstract

Other

Keywords

Other files and links

Fingerprint

Cite this