@Article{RVW79, author = { Ronald L. Rivest and Jean-Paul Van de Wiele }, title = { An {$\Omega((n/\lg n)^{1/2}$} lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integer polynomials }, journal = { Information Processing Letters }, OPTyear = { 1979 }, OPTmonth = { April }, date = { 1979-04 }, volume = { 8 }, number = { 4 }, pages = { 178--180 }, issn = { 0020-0190 }, url = { http://dx.doi.org/10.1016/0020-0190(79)90018-8 }, doi = { 10.1016/0020-0190(79)90018-8 }, acmid = { 1710831 }, publisher = { Elsevier North-Holland, Inc. }, OPTannote = { (No abstract.) }, keywords = { 0-1 polynomials, computational complexity, additive complexity, integer preconditioning, lower bound, polynomial evaluation }, }