LOWER BOUNDS FOR THE COMPLEXITY OF  FUNCTIONS IN A REALISTIC RAM MODEL

Bshouty, Nader H.

LOWER BOUNDS FOR THE COMPLEXITY OF FUNCTIONS IN A REALISTIC RAM MODEL

dc.contributor.author	Bshouty, Nader H.	eng
dc.date.accessioned	2008-02-27T16:49:41Z
dc.date.available	2008-02-27T16:49:41Z
dc.date.computerscience	1999-05-27	eng
dc.date.issued	1995-05-01	eng
dc.description.abstract	This paper develops a new technique that finds lower bounds for the complexity of programs that compute or approximate functions in a realistic RAM model. The nonuniform realistic RAM model is a model that uses the arithmetic operations {+, -, x}, the standard bit operations Shift, Rotate, AND, OR, XOR, NOT (bitwise), comparisons and indirect addressing. We prove general results that give almost tight bounds for the complexity of computing and approximating functions in this model. The functions considered here are integer division, modulo, square root, gcd and logarithms. We also show that if we add the integer division to the realistic RAM model then no nontrivial lower bound can be proven. Our results can be also generalized to probabilistic, nondeterministic and parallel RAM models.	eng
dc.description.notes	We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca	eng
dc.identifier.department	1995-568-20	eng
dc.identifier.doi	http://dx.doi.org/10.11575/PRISM/30480
dc.identifier.uri	http://hdl.handle.net/1880/45751
dc.language.iso	Eng	eng
dc.publisher.corporate	University of Calgary	eng
dc.publisher.faculty	Science	eng
dc.subject	Computer Science	eng
dc.title	LOWER BOUNDS FOR THE COMPLEXITY OF FUNCTIONS IN A REALISTIC RAM MODEL	eng
dc.type	unknown
thesis.degree.discipline	Computer Science	eng