Christian Cachin, Klaus Kursawe, et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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.
Christian Cachin, Klaus Kursawe, et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Victor Shoup, Rosario Gennaro
Journal of Cryptology
Ronald Cramer, Victor Shoup
ACM TISSEC
Ashok K. Chandra, Prabhakar Raghavan, et al.
Computational Complexity