{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:29:07Z","timestamp":1725456547369},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540513711"},{"type":"electronic","value":"9783540462019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/bfb0035783","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T09:00:28Z","timestamp":1133427628000},"page":"559-573","source":"Crossref","is-referenced-by-count":5,"title":["Lower bounds for computations with the floor operation"],"prefix":"10.1007","author":[{"given":"Yishay","family":"Mansour","sequence":"first","affiliation":[]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[]},{"given":"Prasoon","family":"Tiwari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,11,29]]},"reference":[{"key":"36_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison Wesley, Reading, Ma, 1974."},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees. In Proc. 15th ACM Symp. on Theory of Computing, pages 80\u201386, Boston, May 1983.","DOI":"10.1145\/800061.808735"},{"issue":"2","key":"36_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0890-5401(88)90031-4","volume":"78","author":"L. Babai","year":"1988","unstructured":"L. Babai, B. Just, and F. Meyer auf der Heide. On the limits of computations with the floor function. Information and Computation, 78(2):99\u2013107, August 1988.","journal-title":"Information and Computation"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"A. Cobham. The recognition problem for the set of perfect squares. Technical Report RC 1704, IBM T. J. Watson Research Center, Yorktown Heights, April 1966.","DOI":"10.1109\/SWAT.1966.30"},{"issue":"4","key":"36_CR5","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1109\/TC.1985.5009381","volume":"34","author":"E. Dittert","year":"1985","unstructured":"E. Dittert and M. O'Donnell. Lower bounds for sorting with realistic instruction sets. IEEE Transactions on Computers, 34(4):311\u2013317, April 1985. See also, Correction to: Lower bounds for sorting with realistic instruction sets. IEEE Transactions on Computers, 35(10):932, October 1986.","journal-title":"IEEE Transactions on Computers"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"36_CR7","volume-title":"The Numerical Treatment of a Single Nonlinear Equation","author":"A. S. Householder","year":"1970","unstructured":"A. S. Householder. The Numerical Treatment of a Single Nonlinear Equation. McGraw-Hill, New York, NY, 1970."},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(83)90129-9","volume":"24","author":"O. H. Ibarra","year":"1983","unstructured":"O. H. Ibarra, S. Moran, and L. E. Rosier. On the control power of integer division. Theoretical Computer Science, 24:35\u201352, 1983.","journal-title":"Theoretical Computer Science"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"B. Just, F. Meyer auf der Heide, and A. Wigderson. On computations with integer division. 1987. manuscript.","DOI":"10.1007\/BFb0035829"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Y. Mansour, B. Schieber, and P. Tiwari. A lower bound for integer greatest common divisor computations. Technical Report RC 14271, IBM T. J. Watson Research Center, Yorktown Heights, December 1988.","DOI":"10.1109\/SFCS.1988.21921"},{"key":"36_CR11","unstructured":"Y. Mansour, B. Schieber, and P. Tiwari. Lower bounds for computations with the floor function. Technical Report RC 14272, IBM T. J. Watson Research Center, Yorktown Heights, December 1988."},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"Y. Mansour, B. Schieber, and P. Tiwari. Lower bounds for integer greatest common divisor computations. In Proc. 29th IEEE Symp. on Foundation of Computer Science, pages 54\u201363, October 1988.","DOI":"10.1109\/SFCS.1988.21921"},{"key":"36_CR13","unstructured":"W. Paul and J. Simon. Decision trees and random access machines. In Monographie de L'Enseigment Mathematique No. 30, pages 331\u2013340, 1981."},{"key":"36_CR14","volume-title":"A First Course in Numerical Analysis","author":"A. Ralston","year":"1965","unstructured":"A. Ralston. A First Course in Numerical Analysis. McGraw Hill, New York, NY, 1965."},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage. On the power of random access machines. In Proc. 6th ICALP, Lect. Notes. in Comp. Sci. No. 71, pages 520\u2013529, Graz, July 1979.","DOI":"10.1007\/3-540-09510-1_42"},{"issue":"1","key":"36_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(82)90129-6","volume":"14","author":"A. Schmitt","year":"1982","unstructured":"A. Schmitt. On the computational power of the floor function. Information Processing Letters, 14(1):1\u20133, March 1982.","journal-title":"Information Processing Letters"},{"key":"36_CR17","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/0022-0000(81)90041-6","volume":"22","author":"J. Simon","year":"1981","unstructured":"J. Simon. Division in idealized unit cost RAMs. Journal of Comput. and Sys. Sci., 22:421\u2013441, 1981.","journal-title":"Journal of Comput. and Sys. Sci."},{"key":"36_CR18","unstructured":"L. Stockmeyer. Arithmetic versus boolean operations in idealized register machines. Technical Report RC 5954, IBM T. J. Watson Research Center, York-town Heights, April 1976."},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/BF00289512","volume":"1","author":"V. Strassen","year":"1972","unstructured":"V. Strassen. Berechnung und programm i. Acta Inf., 1:320\u2013335, 1972.","journal-title":"Acta Inf."},{"issue":"1","key":"36_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0212001","volume":"12","author":"V. Strassen","year":"1983","unstructured":"V. Strassen. The computational complexity of continued fractions. SIAM J. on Computing, 12(1):1\u201327, February 1983.","journal-title":"SIAM J. on Computing"},{"key":"36_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J.M. Steele","year":"1982","unstructured":"J.M. Steele and A.C. Yao. Lower bounds for algebraic decision trees. Journal of Algorithms, 3:1\u20138, 1982.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:32:04Z","timestamp":1586593924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540513711","9783540462019"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/bfb0035783","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}