{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T04:11:50Z","timestamp":1748664710763,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662486528"},{"type":"electronic","value":"9783662486535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48653-5_1","type":"book-chapter","created":{"date-parts":[[2015,10,2]],"date-time":"2015-10-02T22:46:01Z","timestamp":1443825961000},"page":"1-15","source":"Crossref","is-referenced-by-count":10,"title":["On the Computational Complexity of MapReduce"],"prefix":"10.1007","author":[{"given":"Benjamin","family":"Fish","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Kun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1d\u00e1m D.","family":"Lelkes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lev","family":"Reyzin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,5]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: STOC, pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Beame, P., Koutris, P., Suciu, D.: Communication steps for parallel query processing. In: PODS, pp. 273\u2013284 (2013)","DOI":"10.1145\/2463664.2465224"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Chu, C.-T., Kim, S.K., Lin, Y.-A., Yu, Y., Bradski, G.R., Ng, A.Y., Olukotun, K.: Map-reduce for machine learning on multicore. In: NIPS, pp. 281\u2013288 (2006)","DOI":"10.7551\/mitpress\/7503.003.0040"},{"issue":"1","key":"1_CR4","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Farahat, A.K., Elgohary, A., Ghodsi, A., Kamel, M.S.: Distributed column subset selection on mapreduce. In: ICDM, pp. 171\u2013180 (2013)","DOI":"10.1109\/ICDM.2013.155"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Feldman, J., Muthukrishnan, S., Sidiropoulos, A., Stein, C., Svitkina, Z.: On distributing symmetric streaming computations. ACM Transactions on Algorithms, 6(4) (2010)","DOI":"10.1145\/1824777.1824786"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1006\/jcss.1999.1671","volume":"60","author":"L Fortnow","year":"2000","unstructured":"Fortnow, L.: Time-space tradeoffs for satisfiability. J. Comput. Syst. Sci. 60(2), 337\u2013353 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-25591-5_39","volume-title":"Algorithms and Computation","author":"MT Goodrich","year":"2011","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the mapreduce framework. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 374\u2013383. Springer, Heidelberg (2011)"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: The complexity of k-sat. In: 2012 IEEE 27th Conference on Computational Complexity, p. 237 (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"1_CR10","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Kamara, S., Raykova, M.: Parallel homomorphic encryption. In: Financial Cryptography Workshops, pp. 213\u2013225 (2013)","DOI":"10.1007\/978-3-642-41320-9_15"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: SODA 2010, pp. 938\u2013948. Society for Industrial and Applied Mathematics, Philadelphia (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. In: SPAA 2013, pp. 1\u201310. ACM, New York (2013)","DOI":"10.1145\/2486159.2486168"},{"key":"1_CR14","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS 105, 41\u201372 (2011)","journal-title":"Bulletin of the EATCS"},{"key":"1_CR15","unstructured":"Pace, M.F.: BSP vs mapreduce. In: Proceedings of the International Conference on Computational Science, ICCS 2012, Omaha, Nebraska, USA, June 4\u20136, 2012, pp. 246\u2013255 (2012)"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Sarma, A.D., Afrati, F.N., Salihoglu, S., Ullman, J.D.: Upper and lower bounds on the cost of a map-reduce computation. In: PVLDB 2013, pp. 277\u2013288. VLDB Endowment (2013)","DOI":"10.14778\/2535570.2488334"},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198\u2013200 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Shvachko, K., Kuang, H., Radia, S., Chansler, R.: The hadoop distributed file system. In: Khatib, M.G., He, X., Factor, M. (eds.) MSST, pp. 1\u201310. IEEE Computer Society (2010)","DOI":"10.1109\/MSST.2010.5496972"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Szepietowski, A.: Turing machines with sublogarithmic space. Ernst Schering Research Foundation Workshops. Springer (1994)","DOI":"10.1007\/3-540-58355-6"},{"issue":"8","key":"1_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"1_CR21","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Mathematics and itsApplications. Springer (1986)"},{"issue":"2","key":"1_CR22","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00037-008-0248-y","volume":"17","author":"R Williams","year":"2008","unstructured":"Williams, R.: Time-space tradeoffs for counting NP solutions modulo integers. Computational Complexity 17(2), 179\u2013219 (2008)","journal-title":"Computational Complexity"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48653-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T22:19:29Z","timestamp":1748643569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48653-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662486528","9783662486535"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48653-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}