An optimal lower bound on the number of total operations to compute 0-1 polynomials over the field of complex numbers
Jean-Paul van de Wiele · 1978
We show an Ω(n/log n) lower bound on the total number of operations necessary to compute 0-1 polynomials of degree n in the model with complex preconditioning. The best previous result was Ω(n1/2/log n). This yields the first asymptotically optimal lower bound on the complexity of 0-1 polynomials in this model. We show also that there are 0-1 polynomials of degree n that require Ω(n1/2/log n) additive operations over C. The best previously shown lower bound on additions was Ω(n1/3/log n).