Lower bounds for polynomial evaluation and interpolation problems

Victor Shoup; Roman Smolensky

doi:10.1007/BF01270384

Lower bounds for polynomial evaluation and interpolation problems

Victor Shoup, Roman Smolensky

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We show that there is a set of points p1, p2, . . . , pn such that any arithmetic circuit of depth d for polynomial evaluation (or interpolation) at these points has size Ω (n log n/log(2 + d/log n)). Moreover, for circuits of sub-logarithmic depth d, we obtain a lower bound of Ω(dn^1+1/d) on its size.

Original language	English (US)
Pages (from-to)	301-311
Number of pages	11
Journal	Computational Complexity
Volume	6
Issue number	4
DOIs	https://doi.org/10.1007/BF01270384
State	Published - 1996

ASJC Scopus subject areas

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1007/BF01270384

Cite this

@article{bd1b1659861749579959d015c7f2d984,

title = "Lower bounds for polynomial evaluation and interpolation problems",

abstract = "We show that there is a set of points p1, p2, . . . , pn such that any arithmetic circuit of depth d for polynomial evaluation (or interpolation) at these points has size Ω (n log n/log(2 + d/log n)). Moreover, for circuits of sub-logarithmic depth d, we obtain a lower bound of Ω(dn1+1/d) on its size.",

author = "Victor Shoup and Roman Smolensky",

year = "1996",

doi = "10.1007/BF01270384",

language = "English (US)",

volume = "6",

pages = "301--311",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "4",

}

TY - JOUR

T1 - Lower bounds for polynomial evaluation and interpolation problems

AU - Shoup, Victor

AU - Smolensky, Roman

PY - 1996

Y1 - 1996

N2 - We show that there is a set of points p1, p2, . . . , pn such that any arithmetic circuit of depth d for polynomial evaluation (or interpolation) at these points has size Ω (n log n/log(2 + d/log n)). Moreover, for circuits of sub-logarithmic depth d, we obtain a lower bound of Ω(dn1+1/d) on its size.

AB - We show that there is a set of points p1, p2, . . . , pn such that any arithmetic circuit of depth d for polynomial evaluation (or interpolation) at these points has size Ω (n log n/log(2 + d/log n)). Moreover, for circuits of sub-logarithmic depth d, we obtain a lower bound of Ω(dn1+1/d) on its size.

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

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

U2 - 10.1007/BF01270384

DO - 10.1007/BF01270384

M3 - Article

AN - SCOPUS:0040240146

SN - 1016-3328

VL - 6

SP - 301

EP - 311

JO - Computational Complexity

JF - Computational Complexity

IS - 4

ER -

Lower bounds for polynomial evaluation and interpolation problems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this