On the complexity of computing algebraic functions
Yishay Mansour, Shafi Goldwasser, Baruch Awerbuch · DSpace@MIT (Massachusetts Institute of Technology) · 1990
This research addresses the problem of proving lower bounds on the complexity of algebraic computations involving the floor operation. The model of computation considered is a computation tree with the set of basic operations {+,-,*,*,[.],._ }. The constants available to the computation are 0 and 1, and every other constant needs to be generated explicitly.