Shuhong Gao, Joachim Von Zur Gathen, et al.
Journal of Symbolic Computation
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.
Shuhong Gao, Joachim Von Zur Gathen, et al.
Journal of Symbolic Computation
Erich Kaltofen, Victor Shoup
Mathematics of Computation
Ronald Cramer, Victor Shoup
ACM TISSEC
Victor Shoup
ISSAC 1999