{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:03Z","timestamp":1725664443779},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_125","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:41:38Z","timestamp":1330274498000},"page":"193-204","source":"Crossref","is-referenced-by-count":1,"title":["Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems"],"prefix":"10.1007","author":[{"given":"Sandeep","family":"Sen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing, and C. Yap. Parallel computational geometry. ptoc. of 25th Annual Symposium on Foundations of Computer Science, 468\u2013477, 1985. also appears in full version in Algorithmica, Vol. 3, No. 3, 1988, pp. 293\u2013327.","DOI":"10.1007\/BF01762120"},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1137\/0217074","volume":"17","author":"N. Alon","year":"1988","unstructured":"N. Alon and Y. Azar. The average complexity of deterministic and randomized parallel comparison-sorting algorithms. SIAM Journal on Computing, 17: 1178\u20131192, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/0218035","volume":"18","author":"M.J. Atallah","year":"1989","unstructured":"M.J. Atallah, R. Cole, and M.T. Goodrich. Cascading divide-and-conquer:, a technique for designing parallel algorithms. SIAM Journal on Computing, 18: 499\u2013532, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1137\/0216032","volume":"16","author":"Y. Azar","year":"1987","unstructured":"Y. Azar and U. Vishkin. Tight comparison bounds on the complexity of parallel sorting. SIAM Journal on Computing, 16: 458\u2013464, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"P. Beame and J. Hastad. Optimal bounds for decision problems on CRCW PRAMS. proc. of the Nineteenth ACM STOC, 83\u201393, 1987.","DOI":"10.1145\/28395.28405"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees. proc. of the Fifteenth STOC, 80\u201386, 1983.","DOI":"10.1145\/800061.808735"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson. Applications of random sampling in computational geometry ii. proc of the 4th Annual ACM Symp on Computational Geometry, 1\u201311, 1988.","DOI":"10.1145\/73393.73394"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM Journal on Computing, 17: 770\u2013785, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR9","first-page":"133","volume":"629","author":"M. Dietzfelbinger","year":"1992","unstructured":"M. Dietzfelbinger H. Bast and T. Hagerup. A perfect parallel dictionary. proc. of the 17th Intl. Symp on Math, Foundations of Computer Science, LNCS 629, 133\u2013141, 1992.","journal-title":"Foundations of Computer Science, LNCS"},{"key":"17_CR10","first-page":"259","volume":"577","author":"T. Hagerup","year":"1992","unstructured":"T. Hagerup. The log star revolution. Proc. of the 9th Annual STACS, LNCS 577, 259\u2013278, 1992.","journal-title":"Proc. of the 9th Annual STACS, LNCS"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"T. Hagerup and R. Raman. Waste makes haste: tight bounds for loose, parallel sorting. Proc. of the 33rd Annual FOCS, 628\u2013637, 1992.","DOI":"10.1109\/SFCS.1992.267788"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"S. Kapoor and P. Ramanan. Lower bounds for maximal and convex layer problems. Algorithmica, 447\u2013459, 1989.","DOI":"10.1007\/BF01553901"},{"key":"17_CR13","unstructured":"P. MacKenzie and Q. Stout. Ultra-fasttexpected time parallel algorithms. Proc. of the 2nd SODA, 414\u2013423, 1991."},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/0221031","volume":"21","author":"J.H. Reif","year":"1992","unstructured":"J.H. Reif and S. Sen. Optimal parallel randomized algorithms for 3-d convex hull, and related problems. SIAM Journal on Computing, 21: 466\u2013485, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01758753","volume":"7","author":"J.H. Reif","year":"1992","unstructured":"J.H. Reif and S. Sen. Optimal randomized parallel algorithms for, computational geometry. Algorithmica, 7: 91\u2013117, 1992.","journal-title":"Algorithmica"},{"key":"17_CR16","first-page":"573","volume":"316","author":"M.F. Roy","year":"1992","unstructured":"M.F. Roy and R. Pollack. On the number of cells defined by a set of polynomials. Comptes Rendus, 316: 573\u2013577, 1992.","journal-title":"Comptes Rendus"},{"key":"17_CR17","unstructured":"J. Steele and A.C. Yao. Lower bounds for algebraic decision trees. Journal of Algorithms, 1\u20138, 1982."},{"key":"17_CR18","first-page":"780","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"A.C. Yao. A lower bound for finding convex hulls. Journal of the A.C.M., 28: 780\u2013787, 1981.","journal-title":"Journal of the A.C.M."},{"key":"17_CR19","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01762118","volume":"3","author":"C.K. Yap","year":"1988","unstructured":"C.K. Yap. Parallel triangulation of a polygon in two calls to the, trapezoidal map. Algorithmica, 3: 279\u2013288, 1988.","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_125.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:23:42Z","timestamp":1605648222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_125","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}