Shuhong Gao, Joachim Von Zur Gathen, et al.
Journal of Symbolic Computation
Paper
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.
Related
Ashok K. Chandra, Prabhakar Raghavan, et al.
Computational Complexity
Conference paper
Anonymous credentials on a standard Java card
Patrik Bichsel, Jan Camenisch, et al.
CCS 2009
Christian Cachin, Klaus Kursawe, et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)