{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:07:02Z","timestamp":1743005222187,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382352"},{"type":"electronic","value":"9783642382369"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38236-9_18","type":"book-chapter","created":{"date-parts":[[2013,4,15]],"date-time":"2013-04-15T02:38:02Z","timestamp":1365993482000},"page":"193-204","source":"Crossref","is-referenced-by-count":0,"title":["On the Sublinear Processor Gap for Parallel Architectures"],"prefix":"10.1007","author":[{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"Salinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-15781-3_7","volume-title":"Algorithms \u2013 ESA 2010","author":"D. Ajwani","year":"2010","unstructured":"Ajwani, D., Sitchinava, N., Zeh, N.: Geometric algorithms for private-cache chip multiprocessors. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol.\u00a06347, pp. 75\u201386. Springer, Heidelberg (2010)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Ajwani, D., Sitchinava, N., Zeh, N.: I\/O-optimal distribution sweeping on private-cache chip multiprocessors. In: IPDPS, pp. 1114\u20131123. IEEE (2011)","DOI":"10.1109\/IPDPS.2011.106"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Arge, L., Goodrich, M.T., Nelson, M.J., Sitchinava, N.: Fundamental parallel algorithms for private-cache chip multiprocessors. In: SPAA, pp. 197\u2013206 (2008)","DOI":"10.1145\/1378533.1378573"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Goodrich, M.T., Sitchinava, N.: Parallel external memory graph algorithms. In: IPDPS, pp. 1\u201311. IEEE (2010)","DOI":"10.1109\/IPDPS.2010.5470440"},{"key":"18_CR5","first-page":"487","volume":"194","author":"V. Arlazarov","year":"1970","unstructured":"Arlazarov, V., Dinic, E., Kronrod, M., Faradzev, I.: On economic construction of the transitive closure of a directed graph. Dokl. Akad. Nauk SSSR\u00a0194, 487\u2013488 (1970) (in Russian); English translation in Soviet Math. Dokl. 11, 1209\u20131210 (1975)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Phillips, C.A.: Scheduling DAGs on asynchronous processors. In: SPAA, pp. 35\u201345. ACM (2007)","DOI":"10.1145\/1248377.1248384"},{"key":"18_CR7","unstructured":"Blelloch, G.E., Chowdhury, R.A., Gibbons, P.B., Ramachandran, V., Chen, S., Kozuch, M.: Provably good multicore cache performance for divide-and-conquer algorithms. In: SODA. ACM (2008)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Gibbons, P.B.: Effectively sharing a cache among threads. In: SPAA, pp. 235\u2013244. ACM (2004)","DOI":"10.1145\/1007912.1007948"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1145\/301970.301974","volume":"46","author":"G.E. Blelloch","year":"1999","unstructured":"Blelloch, G.E., Gibbons, P.B., Matias, Y.: Provably efficient scheduling for languages with fine-grained parallelism. J. ACM\u00a046, 281\u2013321 (1999)","journal-title":"J. ACM"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Bose, P., Chen, E.Y., He, M., Maheshwari, A., Morin, P.: Succinct geometric indexes supporting point location queries. In: SODA, pp. 635\u2013644. SIAM (2009)","DOI":"10.1137\/1.9781611973068.70"},{"issue":"2","key":"18_CR11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. J. ACM\u00a021(2), 201\u2013206 (1974)","journal-title":"J. ACM"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Burton, F.W., Sleep, M.R.: Executing functional programs on a virtual tree of processors. In: FPCA, pp. 187\u2013194. ACM (1981)","DOI":"10.1145\/800223.806778"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-efficient dynamic programming algorithms for multicores. In: SPAA, pp. 207\u2013216. ACM (2008)","DOI":"10.1145\/1378533.1378574"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A., Salinger, A.: Optimal speedup on a low-degree multi-core parallel architecture (LoPRAM). In: SPAA, pp. 185\u2013187. ACM (2008)","DOI":"10.1145\/1378533.1378568"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Dymond, P.W., Tompa, M.: Speedups of deterministic machines by synchronous parallel machines. In: STOC, pp. 336\u2013343. ACM (1983)","DOI":"10.1145\/800061.808763"},{"key":"18_CR16","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol.\u00a01. Wiley (1968)"},{"key":"18_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/3-540-45591-4_14","volume-title":"IPDPS 2000 Workshops","author":"A. Fujiwara","year":"2000","unstructured":"Fujiwara, A., Inoue, M., Masuzawa, T.: Parallelizability of some P-complete problems. In: Rolim, J.D.P. (ed.) IPDPS 2000 Workshops. LNCS, vol.\u00a01800, pp. 116\u2013122. Springer, Heidelberg (2000)"},{"key":"18_CR18","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford University Press, Inc., New York (1995)"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Paul, W.J., Valiant, L.G.: On time versus space and related problems. In: FOCS, pp. 57\u201364. IEEE (1975)","DOI":"10.1109\/SFCS.1975.23"},{"issue":"1","key":"18_CR20","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(90)90192-K","volume":"71","author":"C.P. Kruskal","year":"1990","unstructured":"Kruskal, C.P., Rudolph, L., Snir, M.: A complexity theory of efficient parallel algorithms. Theor. Comput. Sci.\u00a071(1), 95\u2013132 (1990)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"18_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/3-540-49543-6_13","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Raab","year":"1998","unstructured":"Raab, M., Steger, A.: \u201cBalls into Bins\u201d - a simple and tight analysis. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol.\u00a01518, pp. 159\u2013170. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38236-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,19]],"date-time":"2023-02-19T11:45:56Z","timestamp":1676807156000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-38236-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382352","9783642382369"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38236-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}