{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T06:51:21Z","timestamp":1672296681505},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1991,4]]},"abstract":"\n It is proved that no finite computation tree with operations { +, -, *, \/, mod, < } can decide whether the greatest common divisor (gcd) of\n a<\/jats:italic>\n and\n b<\/jats:italic>\n is one, for all pairs of integers\n a<\/jats:italic>\n and\n b<\/jats:italic>\n . This settles a problem posed by Gro\u00a8tschel et al. Moreover, if the constants explicitly involved in any operation performed in the tree are restricted to be \u201c0\u201d and \u201c1\u201d (and any other constant must be computed), then we prove an \u03a9(log log\n n<\/jats:italic>\n ) lower bound on the depth of any computation tree with operations { +, -, *, \/, mod, < } that decides whether the gcd of\n a<\/jats:italic>\n and\n b<\/jats:italic>\n is one, for all pairs of\n n<\/jats:italic>\n -bit integers\n a<\/jats:italic>\n and\n b<\/jats:italic>\n .\n <\/jats:p>\n A novel technique for handling the truncation operation is implicit in the proof of this lower bound. In a companion paper, other lower bounds for a large class of problems are proved using a similar technique.<\/jats:p>","DOI":"10.1145\/103516.103522","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"453-471","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["A lower bound for integer greatest common divisor computations"],"prefix":"10.1145","volume":"38","author":[{"given":"Yishay","family":"Mansour","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"Prasoon","family":"Tiwari","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]}],"member":"320","published-online":{"date-parts":[[1991,4]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90031-4"},{"key":"e_1_2_1_2_2","first-page":"82","volume-title":"Proceeding of the 15th A CM Symposium on Theory of Computing","author":"BEN-OR M.","year":"1983","unstructured":"BEN-OR , M. Lower bounds for algebraic computation trees . In Proceeding of the 15th A CM Symposium on Theory of Computing , ( Boston, Mass., Apr. 25-27). ACM, New York , 1983 , pp. 82 - 86 , 10.1145\/800061.808735 BEN-OR, M. Lower bounds for algebraic computation trees. In Proceeding of the 15th A CM Symposium on Theory of Computing, (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp. 82-86, 10.1145\/800061.808735"},{"key":"e_1_2_1_3_2","first-page":"168","volume-title":"Proceedings of the 13th ACM Symposium on Theory of Computing, (Milwaukee, Wisc., May 11-13)","author":"BERTONI A.","year":"1981","unstructured":"BERTONI , A. , MAURI , G. , AND SABADINI , N. A characterization of the class of functions computable in polynomial time on random access machines . In Proceedings of the 13th ACM Symposium on Theory of Computing, (Milwaukee, Wisc., May 11-13) . ACM, New York , 1981 , pp. 168 - 176 . 10.1145\/800076.802470 BERTONI, A., MAURI, G., AND SABADINI, N. A characterization of the class of functions computable in polynomial time on random access machines. In Proceedings of the 13th ACM Symposium on Theory of Computing, (Milwaukee, Wisc., May 11-13). ACM, New York, 1981, pp. 168-176. 10.1145\/800076.802470"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0203001","article-title":"computing time of the Euclidean algorithm","volume":"3","author":"COLLINS G. E.","year":"1974","unstructured":"COLLINS , G. E. The computing time of the Euclidean algorithm . SIAM J. Comput. 3 , 1 ( March 1974 ), 1 - 10. COLLINS, G. E.The computing time of the Euclidean algorithm. SIAM J. Comput. 3, 1 (March 1974), 1 - 10.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_5_2","first-page":"4","article-title":"Lower bounds for sorting with realistic instruction sets","volume":"34","author":"DITTERT E.","year":"1985","unstructured":"DITTERT , E. , AND O'DONNELL , M . Lower bounds for sorting with realistic instruction sets . IEEE Trans. Comput. 34 , 4 ( Apr. 1985 ), 311-317. See also, Correction to: Lower bounds for sorting with realistic instruction sets. IEEE Trans. Comput. 35, 10 (Oct. 1986), 932. DITTERT, E., AND O'DONNELL, M. Lower bounds for sorting with realistic instruction sets. IEEE Trans. Comput. 34, 4 (Apr. 1985), 311-317. See also, Correction to: Lower bounds for sorting with realistic instruction sets. IEEE Trans. Comput. 35, 10 (Oct. 1986), 932.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","volume-title":"Geometric Algorithms and Combinatorial Opthnization","author":"GROTSCHEL M.","year":"1988","unstructured":"GROTSCHEL , M. , LovXsz, L., AND SCHRIJVER , A. Geometric Algorithms and Combinatorial Opthnization . Springer-Verlag , Berlin , 1988 . GROTSCHEL, M., LovXsz, L., AND SCHRIJVER, A. Geometric Algorithms and Combinatorial Opthnization. Springer-Verlag, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(83)90129-9","article-title":"On the control power of integer division","volume":"24","author":"IBARRA H.","year":"1983","unstructured":"IBARRA , 0. H. , MORAN . S. , AND ROSIER , L, E . On the control power of integer division . Theoret. Comput. Sci. 24 ( 1983 ), 35 - 52 . IBARRA, 0. H., MORAN. S., AND ROSIER, L, E. On the control power of integer division. Theoret. Comput. Sci. 24 (1983), 35-52.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1989230101011","article-title":"On computations with integer division","volume":"23","author":"JUST B.","year":"1989","unstructured":"JUST , B. , MEYER AUF DER HEIDE , F. , AND WIGDERSON , A . On computations with integer division . RAIRO Inform. Theor. Appl. 23 , 1 ( 1989 ), 101-111. JUST, B., MEYER AUF DER HEIDE, F., AND WIGDERSON, A. On computations with integer division. RAIRO Inform. Theor. Appl. 23, 1 (1989), 101-111.","journal-title":"RAIRO Inform. Theor. Appl."},{"key":"e_1_2_1_9_2","volume-title":"The Art of Computer Programming","author":"KNUTH D. E.","year":"1981","unstructured":"KNUTH , D. E. The Art of Computer Programming , vol. 2 . Addison-Wesley , Reading, Mass . 2 nd ed., 1981 . KNUTH, D. E. The Art of Computer Programming, vol. 2. Addison-Wesley, Reading, Mass. 2nd ed., 1981.","edition":"2"},{"key":"e_1_2_1_10_2","first-page":"325","volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Oct.). IEEE","author":"MANSOUR Y.","year":"1989","unstructured":"MANSOUR , Y. SCHIEBER , B. , AND TIWARI , P. The complexity of approximating the square root . In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Oct.). IEEE , New York , 1989 , pp. 325 - 330 . MANSOUR, Y. SCHIEBER, B., AND TIWARI, P.The complexity of approximating the square root. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Oct.). IEEE, New York, 1989, pp. 325-330."},{"key":"e_1_2_1_11_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/BFb0035783","volume-title":"Proceedings of the 16th ICALP, (Stresa, Italy, July)","author":"MANSOUR Y.","year":"1989","unstructured":"MANSOUR , Y. , SCHIEBER , B. , AND TIWARJ , P. Lower bounds for computations with the floor operation . In Proceedings of the 16th ICALP, (Stresa, Italy, July) . Lecture Notes in Computer Science , vol. 372 . Springer-Verlag, New York , 1989 , pp. 559 - 573 . Also SIAM J. Comput ., te appear. MANSOUR, Y., SCHIEBER, B., AND TIWARJ, P. Lower bounds for computations with the floor operation. In Proceedings of the 16th ICALP, (Stresa, Italy, July). Lecture Notes in Computer Science, vol. 372. Springer-Verlag, New York, 1989, pp. 559-573. Also SIAM J. Comput., te appear."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4259"},{"key":"e_1_2_1_13_2","volume-title":"Proceedings of the International Symposium held in honor of Ernst Spooker","author":"PAUL W.","year":"1980","unstructured":"PAUL , W. , AND SIMON , J. Decision trees and random access machines . Proceedings of the International Symposium held in honor of Ernst Spooker ( Zurich, Switzerland , 1980 ). In Monographie de L' Enseigment Mathematique, No. 30, Universit6 de Geneva, Geneva, Switzerland, 198i~ pp. 331-340. PAUL, W., AND SIMON, J. Decision trees and random access machines. Proceedings of the International Symposium held in honor of Ernst Spooker (Zurich, Switzerland, 1980). In Monographie de L' Enseigment Mathematique, No. 30, Universit6 de Geneva, Geneva, Switzerland, 198i~ pp. 331-340."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"PRATT V. R. AND STOCKMEYER L. J. A characterization of the power of vector machines. J. Comput. Syst. Sci. 12 (i976) 198-221. PRATT V. R. AND STOCKMEYER L. J. A characterization of the power of vector machines. J. Comput. Syst. Sci. 12 (i976) 198-221.","DOI":"10.1016\/S0022-0000(76)80037-2"},{"key":"e_1_2_1_15_2","series-title":"Lecture Notes in Computer Science","first-page":"520","volume-title":"Proceedings of the 6th ICALf (Graz, Bulgaria, July)","author":"SCH HAGE","year":"1979","unstructured":"SCH (3N HAGE , A. On the power of random access machines . In Proceedings of the 6th ICALf (Graz, Bulgaria, July) . Lecture Notes in Computer Science , vol. 71 , Springer-Verlag , New York . 1979 , pp. 520 - 529 . SCH(3NHAGE, A. On the power of random access machines. In Proceedings of the 6th ICALf (Graz, Bulgaria, July). Lecture Notes in Computer Science, vol. 71, Springer-Verlag, New York. 1979, pp. 520-529."},{"key":"e_1_2_1_16_2","first-page":"28","volume-title":"Inf. Proc. Lett. 8, t (Jan.","author":"SHAMIR A.","year":"1979","unstructured":"SHAMIR , A. Factoring numbers in O(log n) arithmetic steps . Inf. Proc. Lett. 8, t (Jan. 1979 ). 28 - 31 . SHAMIR, A. Factoring numbers in O(log n) arithmetic steps. Inf. Proc. Lett. 8, t (Jan. 1979). 28-31."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/0022-0000(81)90041-6","article-title":"Dwision in idealized unit cost RAMs","volume":"22","author":"SIMON J","year":"1981","unstructured":"SIMON , J . Dwision in idealized unit cost RAMs . J. Comput. Syst. Sci. 22 ( 1981 ), 421 - 444 i. SIMON, J. Dwision in idealized unit cost RAMs. J. Comput. Syst. Sci. 22 (1981), 421-44 i.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF00289512","article-title":"Berechnung und Programm I","volume":"1","author":"STRASSEN V","year":"1972","unstructured":"STRASSEN , V . Berechnung und Programm I . Acta Inf. 1 ( 1972 ), 320 - 335 . STRASSEN, V. Berechnung und Programm I. Acta Inf. 1 (1972), 320-335.","journal-title":"Acta Inf."},{"key":"e_1_2_1_20_2","volume-title":"i (Feb","author":"STRASSEN V.","year":"1983","unstructured":"STRASSEN , V. The computational complexity of continued fractions. SIAM J. Comput. 12 , i (Feb . 1983 ), 1-27. STRASSEN, V.The computational complexity of continued fractions. SIAM J. Comput. 12, i (Feb. 1983), 1-27."},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","article-title":"Lower bounds for algebraic decision trees","volume":"3","author":"STEELE J. M.","year":"1982","unstructured":"STEELE , J. M. , AND YAO , A. C . Lower bounds for algebraic decision trees . J. Alg. 3 ( 1982 ) 1 -- 8 . STEELE, J. M., AND YAO, A. C. Lower bounds for algebraic decision trees. J. Alg. 3 (1982) 1--8.","journal-title":"J. Alg."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/103516.103522","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:28:52Z","timestamp":1672244932000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/103516.103522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["10.1145\/103516.103522"],"URL":"http:\/\/dx.doi.org\/10.1145\/103516.103522","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1991,4]]},"assertion":[{"value":"1991-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}